图属性

在图论中，图属性（graph property）或图常量（graph invariant，又称图不变量）是图的一种性质，它只取决于其抽象结构，而不取决于图的表示形式如特定的图标号或图绘制形式。

定义

虽然图的绘制和图的表示都是图论中的有效课题，但为了只关注图的抽象结构，图属性被定义为在图的所有可能同构下仍存在的属性。换句话说，它是图本身的属性，而不是其特定的绘制或表示形式。非正式用法中，术语“常量”用于定量表示其属性，而“属性”用于定性描述图的特征。例如，语句“图没有度为1的顶点”为“属性”用法，而“图中度为1的顶点数量”为“常量”用法。
更正式地说，图属性是指具有相同属性的一类图，其任何两个同构图要么都属于该类，要么都不属于该类。等价来说，可以使用这类图的指示函数（将图转化为布尔值的函数，属于该类的图为真，否则为假）将图属性形式化，其中任何两个同构图必须具有相同的函数值。类似地，图常量或图参数可以形式化为一个函数，还可从图推广到更广泛的值类，如整数、实数、数字序列或多项式，这些值对应的图其任何两个同构图都具有相同的值。

图常量与图同构

易于计算的图常量有助于快速识别同构图，或者说是识别非同构图。因为对于任何常量，具有不同值的两个图(根据定义)不能是同构的。然而，具有相同常量的两个图可能是同构的，也可能不是同构的。
如果常量I(G)和I(H)恒等，则意味着图G和图H的同构，此时称图常量I(G)是完备的。找到一个可有效计算这种常量的方法(图规范化问题)等价于给出一个简单解决富有挑战性的图同构问题的方法。然而，即使多项式的常量值如色多项式，通常也不完备的。例如，爪形图和4个顶点的道路图都具有相同的色多项式。