While I was reading Reinhard Diestel text on graphs, I came across this paragraph.

Let G = (V, E) and G' = (V' , E' ) be two graphs. We call G and G' isomorphic,and write G $\simeq $ G' , if there exists a bijection φ: V → V with xy ∈ E $ \leftrightarrow $ φ(x)φ(y) ∈ E for all x, y ∈ V . Such a map φ is called an isomorphism; if G = G' , it is called an automorphism.

We do not normally distinguish between isomorphic graphs. Thus, we usually write G = G' rather than G $ \simeq $ G , speak of the complete graph on 17 vertices, and so on.

A map taking graphs as arguments is called a graph invariant if it assigns equal values to isomorphic graphs. The number of vertices and the number of edges of a graph are two simple graph invariants; the greatest number of pairwise adjacent vertices is another.

What does this paragraph mean and what are graph invariants, in simple explanations.

  • 1
    $\begingroup$ A graph invariant is a map on graphs that acts the same on two isomorphic graphs. They define it there. What about it confuses you? $\endgroup$
    – davidlowryduda
    Commented Jun 22, 2015 at 15:20
  • $\begingroup$ The mathematical defination of isomorphism, given above. $\endgroup$ Commented Jun 22, 2015 at 15:21
  • $\begingroup$ examples of graph invariants are things like max-degree (an isomorphism preserves max degree), chromatic number, number of vertices, number of edges, length of longest path, diameter, edge density, number of connected components, and so forth. $\endgroup$
    – TravisJ
    Commented Jun 22, 2015 at 20:00

2 Answers 2


In simple terms, two graphs are isomorphic to each other so long as there is a bijection between the two vertex sets and such that the bijection preserves edges. That is, two graphs $G$ and $G'$ are isomorphic if there exists a bijection, $\phi: V(G) \to V(G')$, and if that bijection also preserves edges. Explicitly, this means that if $uv$ is an edge in $E(G)$, then $\phi (u) \phi (v)$ is an edge in $E(G')$.

One can visualize a graph isomorphism in two ways. 1. Start with a graph and move around vertices in what ever way you want while keeping all the edges in tact. The result, a graph that looks different, but isn't really. 2. A re-labeling of the vertices of $G$. This produces a graph that looks the same, but the vertices are called something else.

Automorphisms are a little bit trickier. The way I look at an automorphism is a moving around of vertices (while keeping edges in tact, as in (1) above) with the caveat that the graph must look exactly the same as before. For example, take $C_4$ with vertex set $V(G) = u_1,u_2,u_3,u_4$ and edge set $E(G) = u_1u_2,u_2u_3,u_3u_4,u_4u_1$ and consider the following bijection.
1. $\phi: V(G) \to V(G')$ where $\phi$ is the permuation $(u_1u_2u_3u_4)$ that sends $u_1 \to u_2$ $u_2 \to u_3$ $u_3 \to u_4$, and $u_4 \to u_1$. (If one is unfamiliar with cycle notation). This is an isomorphism since every edge is preserved, and indeed it is also an automorphism since the resulting graph looks exactly the same as the regular graph. (the permuation above is really just a rotation by 90 degrees if you lay out the original as a "square", as is tradition.


In addition to the above-mentioned definition of a graph invariant, I would like to point out that, according to some authors, a graph invariant may be something different from a number; for example, according to Gross and Yellen (Graph Theory and its Applications, Second Edition, CRC, Boca Raton, 2006, page 89), "a graph invariant is a property of graphs that is preserved by isomorphism". Thus, according to the definition of Gross and Yellen, the degree sequence of a graph is also a graph invariant.

  • $\begingroup$ Well, the degree sequence is also "a map taking graphs as arguments", so I'm not sure what it is that you're objecting to. (I don't think any sources would say that the degree sequence of a graph is not a graph invariant. Thinking of it as a multiset or a sorted sequence, of course.) $\endgroup$ Commented Apr 12 at 17:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .