Graph isomorphism: when two drawings are the same graph

Result 1. Proof. For uv \in E_1, f(u)f(v) \in E_2 by the definition. If \{f(u), f(v)\} = \{f(x), f(y)\} then \{u, v\} = \{x, y\}, as f is one-to-one; so the edge map is one-to-one. Each edge of G_2 is f(u)f(v) for some u, v, as f is onto, and then uv \in E_1 by “exactly when”; so it is onto. For the converse, the map on pairs is one-to-one, so the \lvert E_1 \rvert edges of G_1 go to \lvert E_2 \rvert different edges, all of E_2. A non-edge of G_1 cannot then go to an edge, since that edge is already the image of an edge. \square

Result 2. Proof. u is a neighbor of v exactly when f(u) is a neighbor of f(v), and every vertex of G_2 is some f(u). So f maps the neighbors of v onto those of f(v), one-to-one as f is. As v runs over V_1, f(v) runs over V_2 once each, so the degree lists agree, and each neighbor u of v is matched with the neighbor f(u) of f(v) of the same degree. \square

Result 3. Proof. Consecutive vertices of a walk are adjacent, and f keeps adjacency, so the image is a walk of the same length. A walk (w_0, \ldots, w_k) of G_2 is the image of (f^{-1}(w_0), \ldots, f^{-1}(w_k)), a walk of G_1 by “exactly when”, and of no other, as f is one-to-one. For the same reason the image repeats a vertex exactly where the walk does, so paths go to paths and cycles to cycles. Two vertices are joined exactly when their images are, so f maps each component onto a component. \square

Result 4 is the contrapositive of “if G_1 \cong G_2, the invariant agrees” (A conditional and its contrapositive). Example 3 shows agreement proving nothing.

Result 5. Proof. The identity map is an isomorphism. If f is an isomorphism from G_1 to G_2, then f^{-1} is a bijection (Composing functions between sets, and when an inverse exists), and for x, y \in V_2, xy \in E_2 exactly when f(f^{-1}(x))f(f^{-1}(y)) \in E_2, exactly when f^{-1}(x)f^{-1}(y) \in E_1. If g is an isomorphism from G_2 to G_3, then g \circ f is a bijection and uv \in E_1 exactly when f(u)f(v) \in E_2, exactly when g(f(u))g(f(v)) \in E_3. \square

Result 6. Proof. Let f be a bijection and u \ne v, so f(u) \ne f(v). The statement “uv \in E(G) exactly when f(u)f(v) \in E(H)” is equivalent to its negated form “uv \notin E(G) exactly when f(u)f(v) \notin E(H)”, and for distinct vertices “not an edge” means “an edge of the complement”. So the condition for G and H holds exactly when it holds for \overline{G} and \overline{H}. \square

Result 7. Proof. If G \cong \overline{G}, Result 1 gives \lvert E(G) \rvert = \lvert E(\overline{G}) \rvert, and the two add to \binom{n}{2} (Degree, the handshake lemma and complete graphs, Result 6). So \displaystyle \lvert E(G) \rvert = \frac{n(n-1)}{4} and 4 \mid n(n - 1). One of n and n - 1 is odd and shares no factor with 4, so 4 divides the other: 4 \mid n or 4 \mid n - 1. \square

Result 8. Proof. Let S = \{1, \ldots, n\}. A bijection g : V \to S turns G into the labeled graph g(G) on S with edges g(u)g(v) for uv \in E, and g is an isomorphism onto it. Every labeled graph on S isomorphic to G is g(G) for some g, namely an isomorphism. Fix h. Then g(G) = h(G) exactly when h^{-1} \circ g maps G onto itself, that is, when g = h \circ \alpha for some \alpha \in \operatorname{Aut}(G). So the n! bijections fall into groups of \lvert \operatorname{Aut}(G) \rvert, one group for each labeled copy. \square

Result 9. The counts 11 and 4 are Example 4 and Exercise 6.

1. f(1) = b, f(2) = a, f(3) = d, f(4) = e, f(5) = f, f(6) = c. The edges go to ba, ad, de, ef, fc, cb, be, all seven edges of H, so Result 1 applies. Found from the degree-3 vertices 1, 4 and b, e, each pair joined by an edge lying on two 4-cycles.
2. Every edge of G joins an odd and an even number, so as in Example 2, G has no triangle. The other graph has the triangle 123. By Result 3 they are not isomorphic.
3. A \cong C by 1 \mapsto p, 2 \mapsto r, 3 \mapsto t, 4 \mapsto q, 5 \mapsto s, which sends 12, 23, 34, 45, 51 to pr, rt, tq, qs, sp. B is isomorphic to neither: its degree sequence is (3, 2, 2, 2, 1), theirs (2, 2, 2, 2, 2).
4. Both have degree sequence (2, 2, 2, 2, 1, 1) and 5 edges. G has one component, H two (\{a, b, c\} and \{d, e, f\}); H has a triangle, G no cycle at all.
5. Both have 7 vertices, 7 edges and degree sequence (3, 2, 2, 2, 2, 2, 1). G has a cycle of length 4 and no other cycle; H has one of length 5 and no other. Also, the vertex of degree 3 is at distance 3 from the vertex of degree 1 in G (a, e, f, g) and at distance 2 in H (1, 6, 7); Exercise 15 makes distance an invariant.
6. Four: no edges (\lvert \operatorname{Aut} \rvert = 6, 1 copy), one edge (2, 3 copies), a path of two edges (2, 3 copies), a triangle (6, 1 copy). 1 + 3 + 3 + 1 = 8.
7. 60. \lvert \operatorname{Aut}(C_6) \rvert = 12 by Exercise 16, and \displaystyle \frac{720}{12} = 60. Check: list 1 first and read the cycle from 1; the other 5 labels give 5! = 120 orders, each cycle counted twice (two directions).
8. 12. An isomorphism sends triangle abc to one of the 2 triangles, a to one of its 3 vertices and b to one of the other 2; c is then forced, and the rungs force p, q, r. Each of the 2 \cdot 3 \cdot 2 = 12 choices sends triangle edges to triangle edges and rungs to rungs, so all are isomorphisms.
9. \overline{C_6} joins i and j when they differ by 2, 3 or 4: triangles \{0, 2, 4\} and \{1, 3, 5\} and rungs 03, 14, 25. The map a, b, c, p, q, r \mapsto 0, 2, 4, 3, 5, 1 sends the nine edges of G_1 to 02, 24, 40, 35, 51, 13, 03, 25, 41, all edges. The complement of the Figure 2 graph joins numbers differing by 2 or 4: two disjoint triangles. Since C_6 is connected and two triangles are not, C_6 \not\cong \overline{\text{Figure 2}}, so by Result 6 \overline{C_6} \not\cong Figure 2, that is, Figure 1 \not\cong Figure 2.
10. For the path (w, x, y, z) the complement has edges wy, wz, xz, the path (y, w, z, x); f: w \mapsto y, x \mapsto w, y \mapsto z, z \mapsto x sends wx, xy, yz to yw, wz, zx. A self-complementary graph on 4 vertices has \displaystyle \frac{4 \cdot 3}{4} = 3 edges. Of graphs 5, 6, 7 in Figure 4, graphs 5 and 6 are each other’s complements and have different degree sequences, so only the path remains.
11. The complement has edges ae, bd, cd, ce, de: triangle cde with tails db and ea. The map a \mapsto d, b \mapsto e, c \mapsto c, d \mapsto b, e \mapsto a sends ab, bc, ca, ad, be to de, ec, cd, db, ea, all five edges.
12. n = 12, 13, 16, 17, 20, the n with n \equiv 0 or 1 \pmod 4. For n = 12: \displaystyle \frac{12 \cdot 11}{4} = 33 edges.
13. Six: graphs 6 to 11. Graphs 1 to 5 each have an isolated vertex or two separate edges.
14. There are 2^{10} = 1024 labeled graphs on five vertices. Each class holds \displaystyle \frac{120}{\lvert \operatorname{Aut} \rvert} \le 120 of them, so k classes hold at most 120k. From 120k \ge 1024, k \ge 8.53\ldots, so k \ge 9. (The true count is 34.)
15. By Result 3, walks of length k from u to v correspond one-to-one with walks of length k from f(u) to f(v). So a walk exists for exactly the same lengths, the shortest lengths agree, and if no walk exists on one side none exists on the other, giving \infty on both.
16. Rotations i \mapsto i + s and reflections i \mapsto s - i (modulo n) keep differences of \pm 1, so they are 2n automorphisms, all different for n \ge 3 (a rotation equal to a reflection would need 2i constant). Conversely, an automorphism \alpha has n choices for \alpha(0) and, by Result 2, 2 for \alpha(1), a neighbor of \alpha(0). Then \alpha(2) is the neighbor of \alpha(1) other than \alpha(0), and inductively each \alpha(i + 1) is forced. So there are at most 2n.
17. Take H = G in Result 6: a bijection of V is an isomorphism from G to G exactly when it is one from \overline{G} to \overline{G}.
18. C_3 with C_5 beside it, against two separate copies of C_4: both have 8 vertices, every degree 2 and two components, but only the first has a triangle.
19. First, if G is disconnected then \overline{G} is connected: vertices in different components of G are adjacent in \overline{G}, and two in the same component are both adjacent in \overline{G} to any vertex w of another component. Now let G \cong \overline{G}. If G were disconnected, \overline{G} would be connected, and by Result 3 so would G, a contradiction.
20. In \overline{G} each vertex has degree n - 1 - r. Isomorphic graphs have equal degrees, so r = n - 1 - r and n = 2r + 1 is odd. Result 7 gives n \equiv 0 or 1 \pmod 4, and odd leaves n \equiv 1 \pmod 4. (C_5 is the case r = 2.)