Definitions

# Graph property

In graph theory a graph property is any "inherently graph-theoretical" property of graphs (formal definitions follow), distinguished from properties of graphs described in terms of various graph representations: graph drawings, data structures for graphs, graph labelings, etc.

## Definitions

While graph drawing and graph representation are valid topics in graph theory, in order to focus on "inherently graph-theoretical" properties of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph.

Graphs with the same graph property naturally define a certain family of graphs: the ones that have the specified property. Therefore, to avoid the ambiguity of the English word "property" and a feeling of circular logic in the definition, a graph property is defined as a nonempty proper subset of the set of graphs closed under the graph isomorphism.

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".

Formally, a graph invariant is an indexed family of graph properties.

For example "the number of vertices" is an indexed family of graph properties "a graph has M edges, M = 0, 1, 2....". In this case the family of properties is indexed by the set of nonnegative integer numbers. A more complex example of graph invariant is the degree sequence of a graph: the family of properties is indexed by the set of all ordered sequences of nonnegative integers.