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. The claw graph and the path graph on 4 vertices both have the same chromatic polynomial, for example. Examples Properties Connected graphs Bipartite graphs Planar graphs Triangle-free graphs Perfect graphs Eulerian graphs Hamiltonian graphs Integer invariants Order, the number of vertices Size, the number of edges Number of connected components Circuit rank, a linear combination of the numbers of edges, vertices, and components diameter, the longest of the shortest path lengths between pairs of vertices girth, the length of the shortest cycle Vertex connectivity, the smallest number of vertices whose removal disconnects the graph Edge connectivity, the smallest number of edges whose removal disconnects the graph Chromatic number, the smallest number of colors for the vertices in a proper coloring Chromatic index, the smallest number of colors for the edges in a proper edge coloring Choosability (or list chromatic number), the least number k such that G is k-choosable Independence number, the largest size of an independent set of vertices Clique number, the largest order of a complete subgraph Arboricity Graph genus Pagenumber Hosoya index Wiener index Colin de Verdière graph invariant Boxicity Real number invariants Clustering coefficient Betweenness centrality Fractional chromatic number Algebraic connectivity Isoperimetric number Estrada index Strength Sequences and polynomials Degree sequence Graph spectrum Characteristic polynomial of the adjacency matrix Chromatic polynomial, the number of -colorings viewed as a function of Tutte polynomial, a bivariate function that encodes much of the graph's connectivity See also Hereditary property Logic of graphs, one of several formal languages used to specify graph properties Topological index, a closely related concept in chemical graph theory References Graph theory