Graph property

Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs.

For example, the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant".

[2] Many graph properties are well-behaved with respect to certain natural partial orders or preorders defined on graphs: These definitions may be extended from properties to numerical invariants of graphs: a graph invariant is hereditary, monotone, or minor-closed if the function formalizing the invariant forms a monotonic function from the corresponding partial order on graphs to the real numbers.

A graph invariant I(G) is called complete if the identity of the invariants I(G) and I(H) implies the isomorphism of the graphs G and H. Finding an efficiently-computable such invariant (the problem of graph canonization) would imply an easy solution to the challenging graph isomorphism problem.

However, even polynomial-valued invariants such as the chromatic polynomial are not usually complete.