Ch. 3: Isomorphic Graphs
From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 3.1. The Definition of Isomorphism 3.2. Isomorphism as a Relation 3.3. Excursion: Graphs and Groups 3.4. Excursion: Reconstruction and Solvability
69 flashcards · Mathematics · by lakesare
Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 13 courses
When are two graphs GGG and HHH isomorphic, written G≅HG \cong HG≅H ?
When there is a bijection ϕ:V(G)→V(H)\phi: V(G) \to V(H)ϕ:V(G)→V(H) such that uv∈E(G)uv \in E(G)uv∈E(G) if and only if ϕ(u)ϕ(v)∈E(H)\phi(u)\phi(v) \in E(H)ϕ(u)ϕ(v)∈E(H) . Such a ϕ\phiϕ is an isomorphism from GGG to HHH : adjacent vertices go to adjacent vertices, nonadjacent to nonadjacent. Informally, one graph can be redrawn and relabelled to look exactly like the other.
When are two unlabeled graphs isomorphic?
When, under any labeling of their vertices, they are isomorphic as labeled graphs.
Asked for three graphs of order 5 and size 5, is H1,H2,H3H_1, H_2, H_3H1,H2,H3 an acceptable answer?
No: all three are the 5-cycle C5C_5C5 (they are isomorphic), so this is one graph drawn three ways. Redrawn: e.g. ϕ(u1)=u2, ϕ(v1)=w2, ϕ(w1)=y2, ϕ(x1)=v2, ϕ(y1)=x2\phi(u_1) = u_2, \ \phi(v_1) = w_2, \ \phi(w_1) = y_2, \ \phi(x_1) = v_2, \ \phi(y_1) = x_2ϕ(u1)=u2, ϕ(v1)=w2, ϕ(w1)=y2, ϕ(x1)=v2, ϕ(y1)=x2 is an isomorphism H1→H2H_1 \to H_2H1→H2 .
If G≅HG \cong HG≅H , is the isomorphism from GGG to HHH unique?
Not in general. e.g. from a 5-cycle to a 5-cycle there are 10 isomorphisms (5 rotations, 5 reflections).
Up to isomorphism, how many graphs are there of order 1, 2, 3 and 4?
1, 2, 4 and 11. The eleven graphs of order 4.
Why must two isomorphic graphs have the same order and the same size?
Order: an isomorphism is a bijection between the vertex sets. Size: it maps adjacent pairs exactly onto adjacent pairs. Contrapositive: graphs of different orders or different sizes are not isomorphic.
G1=C6G_1 = C_6G1=C6 and G2=2C3G_2 = 2C_3G2=2C3 both have order 6 and size 6. Are they isomorphic?
No: G2G_2G2 contains a triangle, G1G_1G1 doesn't. An isomorphism ϕ:V(G1)→V(G2)\phi: V(G_1) \to V(G_2)ϕ:V(G1)→V(G2) would need three pairwise adjacent vertices of G1G_1G1 to map onto the triangle u2,v2,z2u_2, v_2, z_2u2,v2,z2 . So same order and same size don't imply isomorphic.
Theorem 3.1 Two graphs GGG and HHH are isomorphic if and only if … ?
Their complements G‾\overline{G}G and H‾\overline{H}H are isomorphic. Since V(G‾)=V(G)V(\overline{G}) = V(G)V(G)=V(G) and V(H‾)=V(H)V(\overline{H}) = V(H)V(H)=V(H) , the same bijection ϕ\phiϕ maps nonadjacent vertices of GGG (adjacent in G‾\overline{G}G ) to nonadjacent vertices of HHH (adjacent in H‾\overline{H}H ).
H1H_1H1 and H2H_2H2 have order 6, size 9, and are both 3-regular. Are they isomorphic?
No: H1H_1H1 contains a triangle ( v1,x1,z1v_1, x_1, z_1v1,x1,z1 ), H2H_2H2 contains none. Alternatively: their complements are C6C_6C6 and 2C32C_32C3 , which aren't isomorphic. ( H2H_2H2 is K3,3K_{3,3}K3,3 .)
A graph GGG with G≅G‾G \cong \overline{G}G≅G is called self-complementary.
Four self-complementary graphs: K1K_1K1 , P4P_4P4 , C5C_5C5 , and a triangle with a pendant edge at two of its vertices.
For which orders nnn can a self-complementary graph exist?
n≡0\boldsymbol{n \equiv 0}n≡0 or 1(mod4)\boldsymbol{1 \pmod 4}1(mod4) GGG and G‾\overline{G}G have the same size and together have (n2)\binom{n}{2}(2n) edges, so GGG has size n(n−1)4\frac{n(n-1)}{4}4n(n−1) , which must be an integer.
Theorem 3.2. If ϕ:V(G)→V(H)\phi: V(G) \to V(H)ϕ:V(G)→V(H) is an isomorphism and u∈V(G)u \in V(G)u∈V(G) , how are degGu\deg_G udegGu and degHϕ(u)\deg_H \phi(u)degHϕ(u) related?
They are equal, so isomorphic graphs have the same degree sequence. If uuu is adjacent to exactly x1,…,xkx_1, \dots, x_kx1,…,xk , then ϕ(u)\phi(u)ϕ(u) is adjacent to exactly ϕ(x1),…,ϕ(xk)\phi(x_1), \dots, \phi(x_k)ϕ(x1),…,ϕ(xk) .
Do two graphs with the same degree sequence have to be isomorphic?
No. C6C_6C6 and 2C32C_32C3 both have degree sequence 2,2,2,2,2,22, 2, 2, 2, 2, 22,2,2,2,2,2 . The complements of these two, the triangular prism and K3,3K_{3,3}K3,3 , both have 3,3,3,3,3,33, 3, 3, 3, 3, 33,3,3,3,3,3 .
Both graphs have degree sequence 4,3,3,2,1,14, 3, 3, 2, 1, 14,3,3,2,1,1 . Is F1≅F2F_1 \cong F_2F1≅F2 ?
No: the degree-4 vertex of F1F_1F1 is adjacent to two end-vertices, the degree-4 vertex of F2F_2F2 isn't. An isomorphism would have to map x1x_1x1 (the only vertex of degree 4) to x2x_2x2 , and map its end-vertex neighbors v1,z1v_1, z_1v1,z1 to end-vertex neighbors of x2x_2x2 .
Both graphs have degree sequence 4,3,3,2,2,24, 3, 3, 2, 2, 24,3,3,2,2,2 . Is H1≅H2H_1 \cong H_2H1≅H2 ?
No: H1H_1H1 has two adjacent vertices of degree 2 ( y1y_1y1 and z1z_1z1 ), H2H_2H2 has none.
ϕ:V(G)→V(H)\phi: V(G) \to V(H)ϕ:V(G)→V(H) is an isomorphism. Which properties of a vertex uuu of GGG must ϕ(u)\phi(u)ϕ(u) share in HHH ?
Every property that doesn't depend on how the graphs are drawn or labeled. e.g. if GGG has a kkk -cycle, so does HHH ; if GGG has a uuu – vvv path of length kkk , then HHH has a ϕ(u)\phi(u)ϕ(u) – ϕ(v)\phi(v)ϕ(v) path of length kkk .
Why is “ G1G_1G1 has eight triangles and G2G_2G2 has seven” a poor argument that G1≇G2G_1 \not\cong G_2G1≅G2 , even if true?
It isn't convincing: the reader can't easily check that every triangle was counted. Better to find a structural difference that is easy to verify.
Theorem 3.5. GGG and HHH are isomorphic graphs. Which two properties hold for GGG if and only if they hold for HHH ?
Being bipartite and being connected.
When are two digraphs D1D_1D1 and D2D_2D2 isomorphic?
When there is a bijection ϕ:V(D1)→V(D2)\phi: V(D_1) \to V(D_2)ϕ:V(D1)→V(D2) with (u,v)∈E(D1)(u, v) \in E(D_1)(u,v)∈E(D1) if and only if (ϕ(u),ϕ(v))∈E(D2)(\phi(u), \phi(v)) \in E(D_2)(ϕ(u),ϕ(v))∈E(D2) . Arcs must be preserved together with their direction.
Theorem 3.6. What kind of relation is isomorphism on the set of all graphs?
An equivalence relation: reflexive, symmetric and transitive. G≅GG \cong GG≅G ; G1≅G2⇒G2≅G1\ G_1 \cong G_2 \Rightarrow G_2 \cong G_1 G1≅G2⇒G2≅G1 ; G1≅G2\ G_1 \cong G_2 G1≅G2 and G2≅G3⇒G1≅G3G_2 \cong G_3 \Rightarrow G_1 \cong G_3G2≅G3⇒G1≅G3 .
Isomorphism is an equivalence relation on the set of all graphs.Which isomorphism does the proof use for each of reflexivity, symmetry and transitivity?
The identity ϵ\epsilonϵ , the inverse ϕ−1\phi^{-1}ϕ−1 , and the composition β∘α\beta \circ \alphaβ∘α . They rely on: the identity is bijective, the inverse of a bijection is bijective, and a composition of bijections is bijective; each also preserves adjacency and nonadjacency.
What are the isomorphism classes of a set of graphs?
The equivalence classes of the isomorphism relation. Two graphs in the same class are isomorphic; two in different classes are not.
How many graphs (up to isomorphism) have degree sequence 2,2,2,2,2,2,2,2,22, 2, 2, 2, 2, 2, 2, 2, 22,2,2,2,2,2,2,2,2 ?
Four: C9C_9C9 , C4∪C5\ C_4 \cup C_5 C4∪C5 , C3∪C6\ C_3 \cup C_6 C3∪C6 , 3C3\ 3C_3 3C3 . A 2-regular graph is a disjoint union of cycles, and 9 splits into parts ≥3\ge 3≥3 as 999 , 4+54 + 54+5 , 3+63 + 63+6 , 3+3+33 + 3 + 33+3+3 .
For unlabeled graphs HHH and GGG , when is HHH isomorphic to a subgraph of GGG ?
When, for any labeling of the vertices of HHH and GGG , the labeled HHH is isomorphic to a subgraph of the labeled GGG . P4P_4P4 is isomorphic to a subgraph of the “bowtie” (two triangles sharing a vertex).
An isomorphism from a graph GGG to itself is called an automorphism of GGG .
The identity ϵ:V(G)→V(G)\epsilon: V(G) \to V(G)ϵ:V(G)→V(G) is always one.
What is the automorphism group Aut(G)\operatorname{Aut}(G)Aut(G) , and why is it a group?
The set of all automorphisms of GGG , under composition. Composition is associative, the identity is an automorphism, inverses of automorphisms are automorphisms, and compositions of automorphisms are automorphisms.
List all automorphisms of HHH in cycle notation.
ϵ, (v1 v2), (v5 v6), (v1 v2)(v5 v6)\boldsymbol{\epsilon, \ (v_1 \ v_2), \ (v_5 \ v_6), \ (v_1 \ v_2)(v_5 \ v_6)}ϵ, (v1 v2), (v5 v6), (v1 v2)(v5 v6) (v1 v2)(v5 v6)(v_1 \ v_2)(v_5 \ v_6)(v1 v2)(v5 v6) swaps v1↔v2v_1 \leftrightarrow v_2v1↔v2 and v5↔v6v_5 \leftrightarrow v_6v5↔v6 and fixes all other vertices. Aut(H)={α1,α2,α3,α4}\operatorname{Aut}(H) = \{\alpha_1, \alpha_2, \alpha_3, \alpha_4\}Aut(H)={α1,α2,α3,α4} and its group table.
Automorphisms of a graph: α4=(v1 v2)(v5 v6)\alpha_4 = (v_1 \ v_2)(v_5 \ v_6)α4=(v1 v2)(v5 v6) and α3=(v5 v6)\alpha_3 = (v_5 \ v_6)α3=(v5 v6) . What is the product α4α3\alpha_4\alpha_3α4α3 ?
(v1 v2)\boldsymbol{(v_1 \ v_2)}(v1 v2) α4α3\alpha_4\alpha_3α4α3 means “first α3\alpha_3α3 , then α4\alpha_4α4 ” (read right to left): v5↦v6↦v5v_5 \mapsto v_6 \mapsto v_5v5↦v6↦v5 , so v5v_5v5 and v6v_6v6 end up fixed.
What are generators of a group, and a generating set?
Elements such that every element of the group is a product of them; the set of them is a generating set. e.g. α=(u v)\alpha = (u \ v)α=(u v) and β=(u v w)\beta = (u \ v \ w)β=(u v w) generate the group of all 6 permutations of {u,v,w}\{u, v, w\}{u,v,w} : β2=(u w v)\beta^2 = (u \ w \ v)β2=(u w v) , βα=(u w)\beta\alpha = (u \ w)βα=(u w) , αβ=(v w)\alpha\beta = (v \ w)αβ=(v w) , α2=ϵ\alpha^2 = \epsilonα2=ϵ .
What is an orbit of a graph GGG ?
For a vertex vvv : the set of all vertices into which vvv can be mapped by some automorphism of GGG . The orbits are the equivalence classes of the relation xRyx \mathrel{R} yxRy if α(x)=y\alpha(x) = yα(x)=y for some α∈Aut(G)\alpha \in \operatorname{Aut}(G)α∈Aut(G) .
Two vertices of a graph that belong to the same orbit are called similar.
To study a structural property of every vertex, one representative per orbit suffices.
What are the orbits of HHH ?
{v1,v2}, {v3}, {v4}, {v5,v6}\boldsymbol{\{v_1, v_2\}, \ \{v_3\}, \ \{v_4\}, \ \{v_5, v_6\}}{v1,v2}, {v3}, {v4}, {v5,v6} The automorphisms are ϵ\epsilonϵ , (v1 v2)(v_1 \ v_2)(v1 v2) , (v5 v6)(v_5 \ v_6)(v5 v6) and (v1 v2)(v5 v6)(v_1 \ v_2)(v_5 \ v_6)(v1 v2)(v5 v6) .
A graph GGG of order nnn has nnn distinct orbits. What is Aut(G)\operatorname{Aut}(G)Aut(G) ?
Only the identity: Aut(G)={ϵ}\operatorname{Aut}(G) = \{\epsilon\}Aut(G)={ϵ} . Every vertex is in an orbit of its own, so every automorphism fixes every vertex. A graph of order 7 with seven orbits.
A graph with a single orbit (every two vertices similar) is called vertex-transitive.
e.g. the complete graphs, the cycles, the complete bipartite graphs Ks,sK_{s,s}Ks,s and the Petersen graph.
Is every vertex-transitive graph regular? Is every regular graph vertex-transitive?
Yes; no. An automorphism maps a vertex only to a vertex of the same degree. Counterexample to the converse, a 3-regular graph where uuu lies on two triangles and www on none, so no automorphism maps uuu to www :
What is a group (A,∘)(A, \circ)(A,∘) ?
A nonempty set AAA with an associative binary operation ∘\circ∘ , an identity eee ( e∘a=a∘e=ae \circ a = a \circ e = ae∘a=a∘e=a ), and an inverse for every element ( b∘a=a∘b=eb \circ a = a \circ b = eb∘a=a∘b=e ). The identity and inverses are necessarily unique.
When is a group (A,∘)(A, \circ)(A,∘) abelian?
When a∘b=b∘aa \circ b = b \circ aa∘b=b∘a for all a,b∈Aa, b \in Aa,b∈A .
Is Aut(F)\operatorname{Aut}(F)Aut(F) , the automorphism group of this graph FFF , abelian?
No. e.g. (u v)(u w)=(u w v)(u \ v)(u \ w) = (u \ w \ v)(u v)(u w)=(u w v) , but (u w)(u v)=(u v w)(u \ w)(u \ v) = (u \ v \ w)(u w)(u v)=(u v w) . Aut(F)\operatorname{Aut}(F)Aut(F) consists of all 6 permutations of {u,v,w}\{u, v, w\}{u,v,w} (fixing x,y,zx, y, zx,y,z ): it is the symmetric group S3S_3S3 .
When are two groups (A,∘)(A, \circ)(A,∘) and (B,∗)(B, \ast)(B,∗) isomorphic?
When there is a bijection ϕ:A→B\phi: A \to Bϕ:A→B with ϕ(x∘y)=ϕ(x)∗ϕ(y)\phi(x \circ y) = \phi(x) \ast \phi(y)ϕ(x∘y)=ϕ(x)∗ϕ(y) for all x,y∈Ax, y \in Ax,y∈A . (B,∘)(B, \circ)(B,∘) with B⊆AB \subseteq AB⊆A is a subgroup of AAA if it is itself a group.
What does Cayley's theorem (on groups) say?
Every group is isomorphic to a group of permutations. The operation in a permutation group is composition. Automorphism groups of graphs are permutation groups.
What is the symmetric group SnS_nSn , and what is its order?
The group of all permutations of a set of nnn elements; order n!\boldsymbol{n!}n! .
GGG is a graph of order nnn . What does ∣Aut(G)∣|\operatorname{Aut}(G)|∣Aut(G)∣ divide, and why?
n!\boldsymbol{n!}n! Aut(G)\operatorname{Aut}(G)Aut(G) is a subgroup of SnS_nSn (permutations of V(G)V(G)V(G) ), and by Lagrange's theorem the order of a subgroup divides the order of the group.
When is a finite group cyclic?
When it has a single generator. A cyclic group of order nnn is {e,a,a2,…,an−1}\{e, a, a^2, \dots, a^{n-1}\}{e,a,a2,…,an−1} .
Which groups are Aut(H)\operatorname{Aut}(H)Aut(H) and Aut(F)\operatorname{Aut}(F)Aut(F) for these two graphs? Are they cyclic?
Aut(H)\operatorname{Aut}(H)Aut(H) : the Klein four group; Aut(F)\operatorname{Aut}(F)Aut(F) : the symmetric group S3S_3S3 . Neither is cyclic. Aut(H)={ϵ,(v1 v2),(v5 v6),(v1 v2)(v5 v6)}\operatorname{Aut}(H) = \{\epsilon, (v_1 \ v_2), (v_5 \ v_6), (v_1 \ v_2)(v_5 \ v_6)\}Aut(H)={ϵ,(v1 v2),(v5 v6),(v1 v2)(v5 v6)} : every element squares to ϵ\epsilonϵ . Aut(F)\ \operatorname{Aut}(F) Aut(F) is all permutations of u,v,wu, v, wu,v,w , and is not even abelian.
What is Aut(C5)\operatorname{Aut}(C_5)Aut(C5) ?
The dihedral group D5D_5D5 of order 10: 5 rotations (including ϵ\epsilonϵ ) and 5 reflections. Generated by the rotation α=(v1 v2 v3 v4 v5)\alpha = (v_1 \ v_2 \ v_3 \ v_4 \ v_5)α=(v1 v2 v3 v4 v5) and the reflection β=(v2 v5)(v3 v4)\beta = (v_2 \ v_5)(v_3 \ v_4)β=(v2 v5)(v3 v4) , with α5=β2=ϵ\alpha^5 = \beta^2 = \epsilonα5=β2=ϵ .
What is the dihedral group DnD_nDn , and what is its order?
The automorphism group of the cycle CnC_nCn ; order 2n\boldsymbol{2n}2n . nnn rotations and nnn reflections. D3=S3D_3 = S_3D3=S3 , since every permutation of C3=K3C_3 = K_3C3=K3 is an automorphism.
A={a1,…,an}A = \{a_1, \dots, a_n\}A={a1,…,an} is a group and Δ\DeltaΔ a generating set. What is the Cayley color digraph DΔ(A)D_\Delta(A)DΔ(A) ?
Vertex set AAA , with an arc (ai,aj)(a_i, a_j)(ai,aj) colored bbb whenever aj=aiba_j = a_ibaj=aib for a generator b∈Δb \in \Deltab∈Δ . The Klein four group with Δ={a2,a4}\Delta = \{a_2, a_4\}Δ={a2,a4} .
In a Cayley color digraph DΔ(A)D_\Delta(A)DΔ(A) ( Δ\DeltaΔ a generating set of the group AAA ), what are the outdegree and indegree of each vertex?
Both are ∣Δ∣|\Delta|∣Δ∣ . For each b∈Δb \in \Deltab∈Δ , there is an arc from aia_iai to aiba_ibaib and an arc into aia_iai from aib−1a_ib^{-1}aib−1 .
Draw the Cayley color digraph of the cyclic group A={e,a,a2,a3}A = \{e, a, a^2, a^3\}A={e,a,a2,a3} with generating set Δ={a}\Delta = \{a\}Δ={a} .
A directed 4-cycle e→a→a2→a3→ee \to a \to a^2 \to a^3 \to ee→a→a2→a3→e , every arc colored aaa . Middle: Δ1={a}\Delta_1 = \{a\}Δ1={a} . Right: Δ2={a,a2}\Delta_2 = \{a, a^2\}Δ2={a,a2} .
What are the color-preserving automorphisms of a Cayley color digraph DDD , and what do they form?
Automorphisms ϕ\phiϕ of DDD such that (u,v)(u, v)(u,v) and (ϕu,ϕv)(\phi u, \phi v)(ϕu,ϕv) have the same color for every arc (u,v)(u, v)(u,v) . They form a subgroup of Aut(D)\operatorname{Aut}(D)Aut(D) .
What question about automorphism groups did Dénes König pose in his 1936 book?
When can a given abstract group be interpreted as the automorphism group of a graph, and how can that graph be constructed? It appears on page 5 of the first book on graph theory.
Frucht's Theorem (Theorem 3.10) For every finite group AAA , there exists … ?
A graph GGG such that Aut(G)\operatorname{Aut}(G)Aut(G) is isomorphic to AAA . This answers König's question: every finite group is the automorphism group of some graph.
How did Roberto Frucht, a group theorist trained by Issai Schur in Berlin, come to graph theory?
He read König's 1936 graph theory book and solved its question on automorphism groups. He was working for an insurance company in Trieste at the time; he later emigrated to Chile and stayed there for the rest of his life.
Frucht's Theorem: for every finite group AAA there is a graph GGG with Aut(G)≅A\operatorname{Aut}(G) \cong AAut(G)≅A .How does the proof build GGG ?
Replace every arc of the Cayley color digraph DΔ(A)D_\Delta(A)DΔ(A) by a path carrying pendant paths whose lengths encode the arc's color and direction. Frucht showed that the color-preserving automorphisms of DΔ(A)D_\Delta(A)DΔ(A) form a group isomorphic to AAA . An arc (u,v)(u, v)(u,v) colored b1b_1b1 becomes (u,u1,v1,v)(u, u_1, v_1, v)(u,u1,v1,v) with a path of length 1 at u1u_1u1 and of length 2 at v1v_1v1 ; for b2b_2b2 , lengths 3 and 4; and so on. Then automorphisms of GGG corresp…
In reconstruction, what is the deck of a graph GGG ?
The unlabeled vertex-deleted subgraphs G−vG - vG−v , one card for each v∈V(G)v \in V(G)v∈V(G) . A deck of five cards.
When is a parameter or property recognizable for a graph GGG ?
When it can be determined from the unlabeled subgraphs G−vG - vG−v , v∈V(G)v \in V(G)v∈V(G) .
Theorem 3.11. Why is the order nnn of every graph recognizable from its deck of subgraphs G−vG - vG−v ?
There are nnn cards (and each card has order n−1n - 1n−1 ).
This is the deck of subgraphs G−vG - vG−v of a graph GGG . What is the size of GGG ?
It can't be determined: GGG is K2K_2K2 (size 1) or K2‾\overline{K_2}K2 (size 0), and both have this deck. So the size of a graph of order 2 is not recognizable.
Theorem 3.12. GGG has order n≥3n \ge 3n≥3 , and G−viG - v_iG−vi has size mim_imi . What is the size mmm of GGG ?
m=∑i=1nmin−2\boldsymbol{m = \dfrac{\sum_{i=1}^n m_i}{n - 2}}m=n−2∑i=1nmi An edge vjvkv_jv_kvjvk appears in every G−viG - v_iG−vi except G−vjG - v_jG−vj and G−vkG - v_kG−vk , so it is counted n−2n - 2n−2 times in ∑mi\sum m_i∑mi .
GGG has order n≥3n \ge 3n≥3 and size mmm , and G−viG - v_iG−vi has size mim_imi . What is degvi\deg v_idegvi ?
degvi=m−mi\boldsymbol{\deg v_i = m - m_i}degvi=m−mi Deleting viv_ivi deletes exactly the edges incident with viv_ivi . Since mmm is recognizable, so is a degree sequence of every graph of order ≥3\ge 3≥3 .
This is the deck of subgraphs G−vG - vG−v of a graph GGG . Find GGG .
A triangle with two pendant edges at the same vertex. n=5n = 5n=5 , m=4+4+3+3+15−2=5m = \frac{4 + 4 + 3 + 3 + 1}{5 - 2} = 5m=5−24+4+3+3+1=5 , degrees m−mi=1,1,2,2,4m - m_i = 1, 1, 2, 2, 4m−mi=1,1,2,2,4 . The vertex removed for card 5 has degree 4, so it is adjacent to all four vertices on that card.
When is a graph GGG of order n≥2n \ge 2n≥2 reconstructible?
When GGG is uniquely determined, up to isomorphism, by its subgraphs G−v1,…,G−vnG - v_1, \dots, G - v_nG−v1,…,G−vn . Neither graph of order 2 is reconstructible: K2K_2K2 and K2‾\overline{K_2}K2 have the same deck.
What does the Reconstruction Conjecture say?
Every graph of order 3 or more is reconstructible. Made around 1941, attributed to Paul Kelly and Stanislaw Ulam (Ulam also developed the Monte Carlo method). Still open.
Two non-isomorphic graphs GGG and HHH of order ≥3\ge 3≥3 have the same deck of subgraphs G−vG - vG−v and H−vH - vH−v . Which properties must they share?
The same order, size and degree sequence, and both are connected or both disconnected. All of these are recognizable. Such a pair would be a counterexample to the Reconstruction Conjecture.
Theorem 3.14. Why is connectedness recognizable for graphs of order ≥3\ge 3≥3 ?
A graph of order ≥3\ge 3≥3 is connected if and only if at least two of its subgraphs G−vG - vG−v are connected. Reason: a graph of order ≥3\ge 3≥3 is connected if and only if it has two distinct vertices u,vu, vu,v with G−uG - uG−u and G−vG - vG−v connected (every connected graph has two such non-cut-vertices, e.g. two leaves of a spanning tree).
In a general reconstruction puzzle, what are a deck and a solution of the deck?
Deck: a set of cards, each with a piece of information about a graph. Solution: any graph satisfying all the information in the deck. A deck can have no solution, a unique solution, or several.
Find all graphs GGG whose subgraphs G−vG - vG−v , v∈V(G)v \in V(G)v∈V(G) , are the graphs on these cards.
None. n=6n = 6n=6 , and the card sizes sum to 6+5+5+4+4+6=306 + 5 + 5 + 4 + 4 + 6 = 306+5+5+4+4+6=30 , so m=306−2=7.5m = \frac{30}{6 - 2} = 7.5m=6−230=7.5 , not an integer.
Find all solutions of this deck.
Exactly one: the bowtie (two triangles sharing a vertex) plus a pendant edge at the shared vertex. Card #4 isn't even needed (a “Joker”).
One subgraph G−v1G - v_1G−v1 has exactly two triangles. Why can these two triangles be neither disjoint nor share an edge?
Disjoint would contradict Card #3; sharing an edge would contradict Card #2. Disjoint: deleting any one vertex leaves a triangle. Sharing an edge (4 vertices): Δ(G)≥5\Delta(G) \ge 5Δ(G)≥5 means GGG has at least 6 vertices, so at least 2 outside those 4, and deleting either one leaves both triangles. So the triangles share one vertex, as in (b).