Ch. 8: Matchings and Factorization

From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 8.1. Matchings 8.2. Factorization 8.3. Decompositions and Graceful Labelings 8.4. Excursion: Instant Insanity 8.5. Excursion: The Petersen Graph 8.6. Exploration: Bi-Graceful Graphs

105 flashcards · Mathematics · by lakesare

Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 13 courses

When is a set of edges independent, and what is a matching?
Independent: no two of the edges are adjacent. A matching is an independent set of edges. Two edges are adjacent when they share a vertex.
GGG is bipartite with partite sets UUU and WWW , ∣U∣≤∣W∣|U| \le |W|∣U∣≤∣W∣ . What does “ UUU can be matched to a subset of WWW ” mean?
GGG has a matching with ∣U∣|U|∣U∣ edges, so every vertex of UUU gets its own neighbor in WWW . Equivalently: a one-to-one function f:U→Wf: U \to Wf:U→W with each f(u)f(u)f(u) adjacent to uuu . No matching of GGG has more than ∣U∣|U|∣U∣ edges.
Six students want one book each, and there is one copy of each book. Their wishes: A: d, h, t; B: g, p, t; C: a, g, h; D: h, p, t; E: a, c, d; F: c, d, p. Can every student get a book they like?
Yes, e.g. A: t, B: g, C: a, D: p, E: d, F: c. A matching with 6 edges in the bipartite graph of students and books:
Seven students apply for jobs (one job each, one opening per job): B: c, e; D: a, c, p, s, t; F: c, r; J: c, e, r; K: a, e, p, s; L: e, r; M: p, r, s, t. Can every student get a job they applied for?
No: B, F, J and L applied only for c, e and r, four students for three jobs. In the bipartite graph, X={B,F,J,L}X = \{B, F, J, L\}X={B,F,J,L} has only 3 neighbors.
GGG is bipartite with partite sets UUU and WWW . What is the neighborhood N(X)N(X)N(X) of a nonempty set X⊆UX \subseteq UX⊆U ?
The set of vertices adjacent to at least one vertex of XXX , i.e. the union of the N(x)N(x)N(x) , x∈Xx \in Xx∈X . So N(X)⊆WN(X) \subseteq WN(X)⊆W .
GGG is bipartite with partite sets UUU and WWW , ∣U∣≤∣W∣|U| \le |W|∣U∣≤∣W∣ . What is Hall's condition?
∣N(X)∣≥∣X∣\boldsymbol{|N(X)| \ge |X|}∣N(X)∣≥∣X∣ for every nonempty subset XXX of UUU . N(X)N(X)N(X) : the vertices adjacent to some vertex of XXX .
Hall's theorem (Theorem 8.3) Let GGG be bipartite with partite sets UUU and WWW , where r=∣U∣≤∣W∣r = |U| \le |W|r=∣U∣≤∣W∣ . Then GGG contains a matching of cardinality rrr if and only if … ?
GGG satisfies Hall's condition: ∣N(X)∣≥∣X∣|N(X)| \ge |X|∣N(X)∣≥∣X∣ for every nonempty X⊆UX \subseteq UX⊆U .
Hall's theorem: a bipartite graph GGG with partite sets UUU and WWW , ∣U∣≤∣W∣|U| \le |W|∣U∣≤∣W∣ , has a matching with ∣U∣|U|∣U∣ edges if and only if ∣N(X)∣≥∣X∣|N(X)| \ge |X|∣N(X)∣≥∣X∣ for every nonempty X⊆UX \subseteq UX⊆U ( N(X)N(X)N(X) : the vertices adjacent to some vertex of XXX ).Why is Hall's condition necessary?
If ∣N(S)∣<∣S∣|N(S)| < |S|∣N(S)∣<∣S∣ , the vertices of SSS have too few neighbors to get distinct partners.
Hall's theorem: a bipartite graph GGG with partite sets UUU and WWW , ∣U∣≤∣W∣|U| \le |W|∣U∣≤∣W∣ , has a matching with ∣U∣|U|∣U∣ edges if and only if ∣N(X)∣≥∣X∣|N(X)| \ge |X|∣N(X)∣≥∣X∣ for every nonempty X⊆UX \subseteq UX⊆U ( N(X)N(X)N(X) : the vertices adjacent to some vertex of XXX ).The proof of “Hall's condition ⇒\Rightarrow⇒ matching” inducts on ∣U∣|U|∣U∣ . Case 1: every S⊆US \subseteq US⊆U with 1≤∣S∣<∣U∣1 \le |S| < |U|1≤∣S∣<∣U∣ has ∣N(S)∣>∣S∣|N(S)| > |S|∣N(S)∣>∣S∣ . How is UUU matched?
Match any u∈Uu \in Uu∈U to a neighbor www , then match U−{u}U - \{u\}U−{u} into W−{w}W - \{w\}W−{w} by induction. Deleting www lowers each ∣N(S)∣|N(S)|∣N(S)∣ by at most 1, so ∣N(S)∣≥∣S∣+1|N(S)| \ge |S| + 1∣N(S)∣≥∣S∣+1 becomes ∣N(S)∣≥∣S∣|N(S)| \ge |S|∣N(S)∣≥∣S∣ : Hall's condition still holds.
Hall's theorem: a bipartite graph GGG with partite sets UUU and WWW , ∣U∣≤∣W∣|U| \le |W|∣U∣≤∣W∣ , has a matching with ∣U∣|U|∣U∣ edges if and only if ∣N(X)∣≥∣X∣|N(X)| \ge |X|∣N(X)∣≥∣X∣ for every nonempty X⊆UX \subseteq UX⊆U ( N(X)N(X)N(X) : the vertices adjacent to some vertex of XXX ).The proof of “Hall's condition ⇒\Rightarrow⇒ matching” inducts on ∣U∣|U|∣U∣ . Case 2: some proper subset XXX of UUU has ∣N(X)∣=∣X∣|N(X)| = |X|∣N(X)∣=∣X∣ . How is UUU matched?
Match XXX onto N(X)N(X)N(X) , and U−XU - XU−X into W−N(X)W - N(X)W−N(X) , both by induction. For S⊆U−XS \subseteq U - XS⊆U−X with S′S'S′ its neighbors outside N(X)N(X)N(X) : ∣N(X)∣+∣S′∣=∣N(X∪S)∣≥∣X∣+∣S∣|N(X)| + |S'| = |N(X \cup S)| \ge |X| + |S|∣N(X)∣+∣S′∣=∣N(X∪S)∣≥∣X∣+∣S∣ , and ∣N(X)∣=∣X∣|N(X)| = |X|∣N(X)∣=∣X∣ gives ∣S′∣≥∣S∣|S'| \ge |S|∣S′∣≥∣S∣ .
Who proved that a bipartite graph has a matching with ∣U∣|U|∣U∣ edges if and only if ∣N(X)∣≥∣X∣|N(X)| \ge |X|∣N(X)∣≥∣X∣ for all nonempty X⊆UX \subseteq UX⊆U , and in what form?
Philip Hall, 1935, as a theorem about sets (systems of distinct representatives), not graphs. Dénes König recognized it as a theorem in graph theory. Hall was an algebraist at Cambridge.
When do nonempty finite sets S1,S2,…,SnS_1, S_2, \dots, S_nS1,S2,…,Sn have a system of distinct representatives?
When there are nnn distinct elements x1,…,xnx_1, \dots, x_nx1,…,xn with xi∈Six_i \in S_ixi∈Si for every iii . Necessary: ∣S1∪⋯∪Sn∣≥n|S_1 \cup \dots \cup S_n| \ge n∣S1∪⋯∪Sn∣≥n .
Do these sets have a system of distinct representatives? {1,3,5,6}, {3,4}, {4,5}, {3,4,5}, {1,2,4,6}, {3,5}\{1,3,5,6\}, \ \{3,4\}, \ \{4,5\}, \ \{3,4,5\}, \ \{1,2,4,6\}, \ \{3,5\}{1,3,5,6}, {3,4}, {4,5}, {3,4,5}, {1,2,4,6}, {3,5}
No: the four sets {3,4},{4,5},{3,4,5},{3,5}\{3,4\}, \{4,5\}, \{3,4,5\}, \{3,5\}{3,4},{4,5},{3,4,5},{3,5} have only 3 elements in their union.
Theorem 8.4 A collection {S1,…,Sn}\{S_1, \dots, S_n\}{S1,…,Sn} of nonempty finite sets has a system of distinct representatives if and only if … ?
For each kkk with 1≤k≤n1 \le k \le n1≤k≤n , the union of any kkk of the sets has at least kkk elements.
Sets S1,…,SnS_1, \dots, S_nS1,…,Sn have distinct representatives if and only if any kkk of them have at least kkk elements in their union.How does this follow from Hall's theorem on bipartite matchings?
Build a bipartite graph: U={S1,…,Sn}U = \{S_1, \dots, S_n\}U={S1,…,Sn} , W=S1∪⋯∪SnW = S_1 \cup \dots \cup S_nW=S1∪⋯∪Sn , and SiS_iSi adjacent to www when w∈Siw \in S_iw∈Si . The union condition is Hall's condition, and a matching of UUU gives each set its own element.
The Marriage Theorem (Theorem 8.5) Among rrr women and rrr men, rrr marriages between acquainted couples are possible if and only if … ?
For each kkk with 1≤k≤r1 \le k \le r1≤k≤r , every kkk women are collectively acquainted with at least kkk men.
What is a maximum matching, and how many edges can a matching in a graph of order nnn have?
A matching of largest cardinality, at most ⌊n/2⌋\boldsymbol{\lfloor n/2 \rfloor}⌊n/2⌋ edges. Each edge uses 2 of the nnn vertices.
What is a perfect matching in a graph of order nnn ?
A matching that covers every vertex: nnn even and n/2n/2n/2 edges. It is necessarily a maximum matching.
Theorem 8.6 (König) Every rrr -regular bipartite graph with r≥1r \ge 1r≥1 has … ?
A perfect matching.
Every rrr -regular bipartite graph ( r≥1r \ge 1r≥1 ) with partite sets UUU , WWW has a perfect matching.Why does Hall's condition hold here?
kkk vertices of UUU send out krkrkr edges, and each vertex of WWW receives at most rrr of them, so they have at least kkk neighbors. Also ∣U∣=∣W∣|U| = |W|∣U∣=∣W∣ : both equal m/rm / rm/r , where mmm is the size.
What is the edge independence number α′(G)\alpha'(G)α′(G) ?
The maximum number of pairwise independent edges, i.e. the size of a maximum matching. A graph of order nnn has a perfect matching if and only if nnn is even and α′(G)=n/2\alpha'(G) = n/2α′(G)=n/2 .
n≥3n \ge 3n≥3 and 1≤r≤s1 \le r \le s1≤r≤s . What are α′(Cn)\alpha'(C_n)α′(Cn) , α′(Kn)\alpha'(K_n)α′(Kn) and α′(Kr,s)\alpha'(K_{r,s})α′(Kr,s) (maximum number of independent edges)?
α′(Cn)=α′(Kn)=⌊n/2⌋\alpha'(C_n) = \alpha'(K_n) = \boldsymbol{\lfloor n/2 \rfloor}α′(Cn)=α′(Kn)=⌊n/2⌋ , α′(Kr,s)=r\ \alpha'(K_{r,s}) = \boldsymbol{r} α′(Kr,s)=r
What is an edge cover of a graph GGG , and the edge covering number β′(G)\beta'(G)β′(G) ?
A set of edges such that every vertex is incident with one of them. β′(G)\beta'(G)β′(G) is the minimum size of an edge cover. A vertex and an incident edge cover each other. β′(G)\beta'(G)β′(G) is defined only when GGG has no isolated vertices.
n≥3n \ge 3n≥3 and 1≤r≤s1 \le r \le s1≤r≤s . What are β′(Cn)\beta'(C_n)β′(Cn) , β′(Kn)\beta'(K_n)β′(Kn) and β′(Kr,s)\beta'(K_{r,s})β′(Kr,s) (minimum number of edges covering all vertices)?
β′(Cn)=β′(Kn)=⌈n/2⌉\beta'(C_n) = \beta'(K_n) = \boldsymbol{\lceil n/2 \rceil}β′(Cn)=β′(Kn)=⌈n/2⌉ , β′(Kr,s)=s\ \beta'(K_{r,s}) = \boldsymbol{s} β′(Kr,s)=s
Theorem 8.7 (Gallai) For every graph GGG of order nnn with no isolated vertices, α′(G)+β′(G)= ?\alpha'(G) + \beta'(G) = \; ?α′(G)+β′(G)=? ( α′\alpha'α′ : maximum number of independent edges; β′\beta'β′ : minimum number of edges covering all vertices.)
n\boldsymbol{n}n e.g. α′(Kr,s)+β′(Kr,s)=r+s\alpha'(K_{r,s}) + \beta'(K_{r,s}) = r + sα′(Kr,s)+β′(Kr,s)=r+s .
For every graph GGG of order nnn without isolated vertices, α′(G)+β′(G)=n\alpha'(G) + \beta'(G) = nα′(G)+β′(G)=n ( α′\alpha'α′ : maximum number of independent edges; β′\beta'β′ : minimum number of edges covering all vertices).Why is α′(G)+β′(G)≤n\alpha'(G) + \beta'(G) \le nα′(G)+β′(G)≤n ?
A maximum matching ( kkk edges) covers 2k2k2k vertices; one more edge for each of the other n−2kn - 2kn−2k vertices gives an edge cover with n−kn - kn−k edges.
For every graph GGG of order nnn without isolated vertices, α′(G)+β′(G)=n\alpha'(G) + \beta'(G) = nα′(G)+β′(G)=n ( α′\alpha'α′ : maximum number of independent edges; β′\beta'β′ : minimum number of edges covering all vertices).Why is α′(G)+β′(G)≥n\alpha'(G) + \beta'(G) \ge nα′(G)+β′(G)≥n ?
A minimum edge cover ( ℓ\ellℓ edges) forms a spanning forest of stars with n−ℓn - \elln−ℓ components; one edge from each star is a matching of n−ℓn - \elln−ℓ edges. The cover's edges contain no trail of length 3, since its middle edge could be dropped from the cover. So no cycles and no paths of length 3: every component is a star.
What is the vertex independence number α(G)\alpha(G)α(G) , and what is a maximum independent set?
α(G)\alpha(G)α(G) is the maximum number of pairwise nonadjacent vertices; a maximum independent set is an independent set of α(G)\alpha(G)α(G) vertices. Also just called the independence number.
What is a vertex cover of GGG , and the vertex covering number β(G)\beta(G)β(G) ?
A set of vertices such that every edge is incident with one of them. β(G)\beta(G)β(G) is the minimum size of a vertex cover.
n≥3n \ge 3n≥3 and 1≤r≤s1 \le r \le s1≤r≤s . What are α\alphaα (maximum independent vertices) and β\betaβ (minimum vertex cover) of CnC_nCn , KnK_nKn and Kr,sK_{r,s}Kr,s ?
α\alphaα : ⌊n/2⌋, 1, s\boldsymbol{\lfloor n/2 \rfloor, \ 1, \ s}⌊n/2⌋, 1, s . β\ \beta β : ⌈n/2⌉, n−1, r\boldsymbol{\lceil n/2 \rceil, \ n - 1, \ r}⌈n/2⌉, n−1, r . In each case α+β\alpha + \betaα+β is the order.
Theorem 8.8 (Gallai) For every graph GGG of order nnn with no isolated vertices, α(G)+β(G)= ?\alpha(G) + \beta(G) = \; ?α(G)+β(G)=? ( α\alphaα : maximum number of independent vertices; β\betaβ : minimum number of vertices covering all edges.)
n\boldsymbol{n}n A set SSS of vertices is independent exactly when V(G)−SV(G) - SV(G)−S covers every edge.
The equations α′(G)+β′(G)=n\alpha'(G) + \beta'(G) = nα′(G)+β′(G)=n and α(G)+β(G)=n\alpha(G) + \beta(G) = nα(G)+β(G)=n are called the Gallai identities.
Tibor Gallai (1912–1992), Hungarian; he helped König with his graph theory book and was among the first to see the importance of min-max theorems.
G=K1+2K3G = K_1 + 2K_3G=K1+2K3 ( www joined to two triangles). Find α′(G)\alpha'(G)α′(G) , β′(G)\beta'(G)β′(G) , α(G)\alpha(G)α(G) , β(G)\beta(G)β(G) .
α′=3, β′=4, α=2, β=5\boldsymbol{\alpha' = 3, \ \beta' = 4, \ \alpha = 2, \ \beta = 5}α′=3, β′=4, α=2, β=5 α′≤⌊7/2⌋\alpha' \le \lfloor 7/2 \rfloorα′≤⌊7/2⌋ , attained by {tu,vw,yz}\{tu, vw, yz\}{tu,vw,yz} . www is adjacent to all other vertices, and an independent set has at most one vertex per triangle: α=2\alpha = 2α=2 , e.g. {t,z}\{t, z\}{t,z} . Then β′=7−3\beta' = 7 - 3β′=7−3 and β=7−2\beta = 7 - 2β=7−2 by the Gallai identities.
What is a 1-factor of a graph GGG ?
A 1-regular spanning subgraph of GGG . Its edge set is a perfect matching, so GGG has a 1-factor if and only if GGG has a perfect matching.
When does Kr,sK_{r,s}Kr,s have a 1-factor? And CnC_nCn and KnK_nKn ?
Kr,sK_{r,s}Kr,s : if and only if r=sr = sr=s . Cn\ C_n Cn and KnK_nKn : if and only if nnn is even.
Find a 1-factor of the Petersen graph.
The five spokes u1v1,u2v2,…,u5v5u_1v_1, u_2v_2, \dots, u_5v_5u1v1,u2v2,…,u5v5 .
Why does every Hamiltonian graph of even order have a 1-factor?
Every other edge of a Hamiltonian cycle forms a perfect matching. The remaining edges of the cycle form a second one, so it even has two disjoint perfect matchings.
What is an odd component of a graph, and what does ko(G)k_o(G)ko(G) denote?
A component of odd order. ko(G)k_o(G)ko(G) is the number of odd components of GGG .
This graph HHH is 3-regular of order 16. Why has it no 1-factor?
H−vH - vH−v has three odd components, but the one 1-factor edge at vvv reaches only one of them. The other two would need 1-factors of their own, impossible for odd order. In general: if ko(G−S)>∣S∣k_o(G - S) > |S|ko(G−S)>∣S∣ for some SSS , then GGG has no 1-factor.
Tutte's theorem (Theorem 8.10) A graph GGG contains a 1-factor if and only if … ?
ko(G−S)≤∣S∣\boldsymbol{k_o(G - S) \le |S|}ko(G−S)≤∣S∣ for every proper subset SSS of V(G)V(G)V(G) . kok_oko : number of odd components. S=∅S = \emptysetS=∅ gives ko(G)=0k_o(G) = 0ko(G)=0 , so GGG has even order.
Tutte's theorem: a graph GGG has a 1-factor if and only if ko(G−S)≤∣S∣k_o(G - S) \le |S|ko(G−S)≤∣S∣ for every proper subset SSS of V(G)V(G)V(G) ( kok_oko : number of components of odd order).Why does a 1-factor FFF force ko(G−S)≤∣S∣k_o(G - S) \le |S|ko(G−S)≤∣S∣ ?
An odd component of G−SG - SG−S can't be matched within itself, so an edge of FFF joins it to SSS , and these edges end at distinct vertices of SSS .
Tutte's theorem: a graph GGG has a 1-factor if and only if ko(G−S)≤∣S∣k_o(G - S) \le |S|ko(G−S)≤∣S∣ for every proper subset SSS of V(G)V(G)V(G) ( kok_oko : number of components of odd order).The converse is proved by induction on the even order. Which set SSS does the proof work with, and what does G−SG - SG−S look like?
A largest set SSS with ko(G−S)=∣S∣k_o(G - S) = |S|ko(G−S)=∣S∣ . Then G−SG - SG−S has only odd components, exactly ∣S∣|S|∣S∣ of them. Such sets exist: {v}\{v\}{v} with vvv not a cut-vertex. An even component of G−SG - SG−S would have a non-cut-vertex u0u_0u0 , and S∪{u0}S \cup \{u_0\}S∪{u0} would be a larger such set.
Proof of Tutte's theorem, by induction on the even order of GGG : SSS is a largest set of vertices with ko(G−S)=∣S∣k_o(G - S) = |S|ko(G−S)=∣S∣ ( kok_oko : number of odd components), so G−SG - SG−S consists of odd components G1,…,GkG_1, \dots, G_kG1,…,Gk , k=∣S∣k = |S|k=∣S∣ .How does the proof match each GiG_iGi to its own vertex of SSS ?
With distinct representatives viv_ivi of the sets SiS_iSi = vertices of SSS adjacent to GiG_iGi , giving edges uiviu_iv_iuivi with ui∈Giu_i \in G_iui∈Gi . The union condition holds: if jjj of the SiS_iSi had a union TTT with ∣T∣<j|T| < j∣T∣<j , then ko(G−T)≥j>∣T∣k_o(G - T) \ge j > |T|ko(G−T)≥j>∣T∣ .
Proof of Tutte's theorem, by induction on the even order of GGG : SSS is a largest set of vertices with ko(G−S)=∣S∣k_o(G - S) = |S|ko(G−S)=∣S∣ ( kok_oko : number of odd components), so G−SG - SG−S consists of odd components G1,…,GkG_1, \dots, G_kG1,…,Gk , k=∣S∣k = |S|k=∣S∣ .Each GiG_iGi is matched to SSS by an edge uiviu_iv_iuivi . Why does Gi−uiG_i - u_iGi−ui have a 1-factor?
By induction. If some WWW had ko(Gi−ui−W)>∣W∣k_o(G_i - u_i - W) > |W|ko(Gi−ui−W)>∣W∣ , parity gives ≥∣W∣+2\ge |W| + 2≥∣W∣+2 , and then S′=S∪W∪{ui}S' = S \cup W \cup \{u_i\}S′=S∪W∪{ui} has ko(G−S′)=∣S′∣k_o(G - S') = |S'|ko(G−S′)=∣S′∣ , contradicting the choice of SSS . The 1-factors of all Gi−uiG_i - u_iGi−ui together with the edges uiviu_iv_iuivi form a 1-factor of GGG .
Which wartime achievement is W. T. Tutte known for?
At Bletchley Park, he worked out the structure of the German army's “Fish” cipher machine from intercepted messages alone. Tony Sale called it the “greatest intellectual feat of the whole war”. After the war, as a graduate student, Tutte published his characterization of graphs with 1-factors.
Petersen's theorem (Theorem 8.11) Every 3-regular bridgeless graph contains … ?
A 1-factor. It came before Tutte's theorem historically, but Tutte's theorem gives a simpler proof.
Petersen's theorem: every 3-regular bridgeless graph GGG has a 1-factor. The proof checks Tutte's condition ko(G−S)≤∣S∣k_o(G - S) \le |S|ko(G−S)≤∣S∣ ( kok_oko : number of odd components).How?
Each odd component of G−SG - SG−S is joined to SSS by an odd number of edges, so (no bridges) by at least 3; but SSS sends out at most 3∣S∣3|S|3∣S∣ edges, so 3ko(G−S)≤3∣S∣3 k_o(G - S) \le 3|S|3ko(G−S)≤3∣S∣ . Odd number: the degrees in GGG of the vertices of an odd component GiG_iGi sum to 3∣V(Gi)∣3|V(G_i)|3∣V(Gi)∣ , which is odd, and equal 2∣E(Gi)∣2|E(G_i)|2∣E(Gi)∣ plus the number of edges from GiG_iGi to SSS .
Every 3-regular graph with at most two bridges contains a 1-factor.
Sharp: the 3-regular graph below has three bridges and no 1-factor.
When is a graph 1-factorable, and what is a 1-factorization?
GGG is 1-factorable if E(G)E(G)E(G) can be partitioned into the edge sets of 1-factors F1,…,FrF_1, \dots, F_rF1,…,Fr ; these form a 1-factorization. So every edge lies in exactly one FiF_iFi .
Why is every 1-factorable graph regular?
Each vertex lies on exactly one edge of each of the rrr 1-factors, so it has degree rrr . The converse fails: there are 3-regular graphs with no 1-factor at all.
In 1884 Tait claimed that every 3-regular graph is 1-factorable, “not true without limitation”. What did Petersen show in 1898?
Even a 3-regular bridgeless graph need not be 1-factorable: the Petersen graph isn't.
Why is the Petersen graph not 1-factorable?
Two of the three 1-factors would form a 2-regular spanning subgraph; with no Hamiltonian cycle and no cycle shorter than 5, it must be 2C52C_52C5 , which has no 1-factor. Yet it contains both of those 1-factors, a contradiction. ( 2C52C_52C5 : two disjoint 5-cycles; an odd cycle has no perfect matching.)
How is K2kK_{2k}K2k factored into 1-factors?
Put v1,…,v2k−1v_1, \dots, v_{2k-1}v1,…,v2k−1 on a regular (2k−1)(2k-1)(2k−1) -gon and v0v_0v0 at its center; FiF_iFi is the edge v0viv_0v_iv0vi plus all edges perpendicular to v0viv_0v_iv0vi . The 1-factorization of K6K_6K6 .
In the 1-factorization of K2kK_{2k}K2k by edges perpendicular to v0viv_0v_iv0vi , each 1-factor is the previous one rotated by 2π/(2k−1)2\pi/(2k-1)2π/(2k−1) , so it is called a cyclic factorization.
Theorem 8.15. Why is every rrr -regular bipartite graph ( r≥1r \ge 1r≥1 ) 1-factorable?
Remove a perfect matching: what is left is (r−1)(r-1)(r−1) -regular bipartite. Repeat rrr times. Each step uses that every regular bipartite graph of positive degree has a perfect matching.
What is a 2-factor of GGG , and when is GGG 2-factorable?
A 2-factor is a spanning 2-regular subgraph (disjoint cycles covering all vertices). 2-factorable: E(G)E(G)E(G) can be partitioned into the edge sets of 2-factors.
Theorem 8.16 (Petersen) A graph GGG is 2-factorable if and only if … ?
GGG is rrr -regular for some positive even integer rrr . “Only if”: each 2-factor contributes 2 to every degree. So K2k+1K_{2k+1}K2k+1 , being 2k2k2k -regular, is 2-factorable.
Every 2k2k2k -regular graph GGG , with vertices v1,…,vnv_1, \dots, v_nv1,…,vn , is 2-factorable. The proof may assume GGG connected, so GGG has an Eulerian circuit CCC .Which bipartite graph HHH does the proof build, and why is HHH kkk -regular?
U={u1,…,un}U = \{u_1, \dots, u_n\}U={u1,…,un} , W={w1,…,wn}W = \{w_1, \dots, w_n\}W={w1,…,wn} , with uiwju_i w_juiwj an edge when vjv_jvj immediately follows viv_ivi on CCC . Each vertex of GGG appears kkk times on CCC . So HHH is a kkk -regular bipartite graph, hence 1-factorable. G=K2,2,2G = K_{2,2,2}G=K2,2,2 , its HHH , a 1-factorization of HHH , and the 2-factorization of GGG it gives.
Proof that a 2k2k2k -regular graph GGG with vertices v1,…,vnv_1, \dots, v_nv1,…,vn is 2-factorable: HHH is bipartite with partite sets {u1,…,un}\{u_1, \dots, u_n\}{u1,…,un} , {w1,…,wn}\{w_1, \dots, w_n\}{w1,…,wn} and uiwju_iw_juiwj an edge when vjv_jvj follows viv_ivi on an Eulerian circuit of GGG .Why does each 1-factor of HHH give a 2-factor of GGG ?
It gives each viv_ivi one successor vjv_jvj (a neighbor) and each vjv_jvj one predecessor, a permutation of V(G)V(G)V(G) whose cycles are disjoint cycles of GGG covering every vertex. No cycles of length 1 or 2: GGG has no loops, and the circuit uses each edge once, in one direction. Distinct 1-factors of HHH use distinct edges of GGG .
What is a Hamiltonian factorization of a graph?
A 2-factorization in which every 2-factor is a Hamiltonian cycle. A graph with one is Hamiltonian-factorable. Hamiltonian factorizations of K3K_3K3 , K5K_5K5 and K7K_7K7 .
The vertices of KnK_nKn lie on a cycle C=(v1,…,vn,v1)C = (v_1, \dots, v_n, v_1)C=(v1,…,vn,v1) , and each edge vivjv_iv_jvivj is labelled with the distance dC(vi,vj)d_C(v_i, v_j)dC(vi,vj) on CCC . For odd nnn , how many edges get each label?
Exactly nnn edges for each label 1,2,…,(n−1)/21, 2, \dots, (n-1)/21,2,…,(n−1)/2 . For even nnn : nnn edges for each label 1,…,(n−2)/21, \dots, (n-2)/21,…,(n−2)/2 , and n/2n/2n/2 edges labelled n/2n/2n/2 .
Theorem 8.17 For every integer k≥1k \ge 1k≥1 , the complete graph K2k+1K_{2k+1}K2k+1 is … ?
Hamiltonian-factorable: it factors into kkk Hamiltonian cycles.
How is a Hamiltonian factorization of K2k+1K_{2k+1}K2k+1 constructed?
v1,…,v2kv_1, \dots, v_{2k}v1,…,v2k on a regular 2k2k2k -gon, v0v_0v0 inside. Take the zig-zag path v1,v2,v2k,v3,v2k−1,…,vk+1v_1, v_2, v_{2k}, v_3, v_{2k-1}, \dots, v_{k+1}v1,v2,v2k,v3,v2k−1,…,vk+1 , close it through v0v_0v0 , and rotate by π/k\pi/kπ/k , kkk times. K9K_9K9 : edge labels are distances on the 8-gon, 0 at v0v_0v0 . The cycle has two edges of each label 0,…,k−10, \dots, k-10,…,k−1 and one of label kkk , so the kkk rotations use every edge once.
What is a factor of GGG , and when is GGG FFF -factorable?
A factor is a spanning subgraph. GGG is FFF -factorable if E(G)E(G)E(G) can be partitioned into factors, each isomorphic to FFF . For order nnn : 1-factorable means (n/2)K2(n/2)K_2(n/2)K2 -factorable, and Hamiltonian-factorable means CnC_nCn -factorable.
How is K9K_9K9 factored into four copies of 3K33K_33K3 (three disjoint triangles)?
v1,…,v8v_1, \dots, v_8v1,…,v8 on a regular 8-gon, v0v_0v0 inside; one 3K33K_33K3 with two edges of each label 0, 1, 2, 3 and one of label 4, rotated by π/4\pi/4π/4 three times. So nine schoolgirls can take four daily walks in three rows of three with no two in the same row twice.
Kirkman's Schoolgirl Problem (1850): 15 girls walk daily in five rows of three. Can they do so for a week with no two girls in the same row twice? What is this in graph terms?
A 5K35K_35K3 -factorization of K15K_{15}K15 , with one factor per day. It exists. 7 days, since each girl walks with 2 of the other 14 per day. There is no cyclic 5K35K_35K3 -factorization of K15K_{15}K15 , which makes one harder to find.
KnK_nKn has a tK3tK_3tK3 -factorization (every factor consists of ttt disjoint triangles). Why must n=6k+3n = 6k + 3n=6k+3 ?
n=3tn = 3tn=3t , and each factor uses 2 of the n−1n - 1n−1 edges at a vertex, so nnn is odd; hence ttt is odd. t=2k+1t = 2k + 1t=2k+1 gives n=6k+3n = 6k + 3n=6k+3 .
What is a Kirkman triple system of order nnn ?
A set SSS of nnn elements with a collection TTT of 3-element subsets (triples) such that every two elements lie in a unique triple, plus a partition of TTT into classes, each containing every element exactly once. Exactly a (2k+1)K3(2k+1)K_3(2k+1)K3 -factorization of K6k+3K_{6k+3}K6k+3 (triples = triangles, classes = factors).
Theorem 8.19 A Kirkman triple system of order n≥3n \ge 3n≥3 exists if and only if … ?
n≡3(mod6)\boldsymbol{n \equiv 3 \pmod 6}n≡3(mod6) Ray-Chaudhuri and Wilson, 1971.
Theorem 8.20 For every integer k≥1k \ge 1k≥1 , the complete graph K2kK_{2k}K2k can be factored into … ?
k−1k - 1k−1 Hamiltonian cycles and a 1-factor. K8K_8K8 : three Hamiltonian cycles G1,G2,G3G_1, G_2, G_3G1,G2,G3 and the 1-factor G4G_4G4 . K2kK_{2k}K2k ( k≥2k \ge 2k≥2 ) itself is not Hamiltonian-factorable: its degree 2k−12k - 12k−1 is odd.
When is GGG decomposable into subgraphs H1,…,HkH_1, \dots, H_kH1,…,Hk , and when is it HHH -decomposable?
When E(H1),…,E(Hk)E(H_1), \dots, E(H_k)E(H1),…,E(Hk) partition E(G)E(G)E(G) . HHH -decomposable: such a decomposition with every HiH_iHi isomorphic to HHH . Unlike factors, the HiH_iHi need not be spanning subgraphs.
Why must n≡1n \equiv 1n≡1 or 3(mod6)3 \pmod 63(mod6) when KnK_nKn is K3K_3K3 -decomposable?
3 divides the size n(n−1)/2n(n-1)/2n(n−1)/2 , and each vertex lies in (n−1)/2(n-1)/2(n−1)/2 triangles, so nnn is odd. nnn odd with 3∣n3 \mid n3∣n or 3∣n−13 \mid n - 13∣n−1 means n≡3n \equiv 3n≡3 or 1(mod6)1 \pmod 61(mod6) .
What is a Steiner triple system of order nnn ?
A set SSS of nnn elements with a collection of 3-element subsets (triples) such that every two elements lie in exactly one triple. One exists exactly when KnK_nKn is K3K_3K3 -decomposable (triples = triangles).
Theorem 8.21 (Kirkman, 1846) A Steiner triple system of order n≥3n \ge 3n≥3 exists if and only if … ?
n≡1 or 3(mod6)\boldsymbol{n \equiv 1 \text{ or } 3 \pmod 6}n≡1 or 3(mod6)
How can K7K_7K7 be decomposed into triangles?
v1,…,v7v_1, \dots, v_7v1,…,v7 on a regular 7-gon: the triangle v1v2v4v_1v_2v_4v1v2v4 , with one edge of each length 1, 2, 3, and its rotations by 2π/72\pi/72π/7 . The Steiner triple system {1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,1,3}\{1,2,4\}, \{2,3,5\}, \{3,4,6\}, \{4,5,7\}, \{5,6,1\}, \{6,7,2\}, \{7,1,3\}{1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,1,3} ; a cyclic decomposition.
Why is it unfair that Steiner triple systems are named after Steiner?
Kirkman proved they exist (1846), seven years before Steiner asked whether they exist. Kirkman also thought of Hamiltonian cycles before Hamilton.
What did Ringel conjecture in 1967 about trees and complete graphs?
If TTT is a tree of size mmm , then K2m+1K_{2m+1}K2m+1 is TTT -decomposable. The book calls it unsettled; Montgomery, Pokrovskiy and Sudakov proved it for all large mmm in 2020.
GGG has size mmm . What is a graceful labeling of GGG ?
A one-to-one f:V(G)→{0,1,…,m}f: V(G) \to \{0, 1, \dots, m\}f:V(G)→{0,1,…,m} such that the edge labels ∣f(u)−f(v)∣|f(u) - f(v)|∣f(u)−f(v)∣ are all different, i.e. exactly 1,…,m1, \dots, m1,…,m . A graph with a graceful labeling is graceful. Graceful labelings of K3K_3K3 , K4K_4K4 , C4C_4C4 and two more graphs.
fff is a graceful labeling of a graph of size mmm . Which other labeling is then graceful too?
The complementary labeling g(v)=m−f(v)g(v) = m - f(v)g(v)=m−f(v) . ∣g(u)−g(v)∣=∣f(u)−f(v)∣|g(u) - g(v)| = |f(u) - f(v)|∣g(u)−g(v)∣=∣f(u)−f(v)∣ .
Why is C5C_5C5 not graceful?
Edge labels 5 and 4 force (up to the complementary labeling) a path labelled 4, 0, 5, and then no labels for the last two vertices work. Label 5 needs 0 and 5 adjacent; label 4 needs 0 and 4, or 1 and 5, adjacent. Faster: ∣a−b∣≡a+b(mod2)|a - b| \equiv a + b \pmod 2∣a−b∣≡a+b(mod2) , so around a cycle the edge labels have even sum, but 1+2+3+4+5=151 + 2 + 3 + 4 + 5 = 151+2+3+4+5=15 .
What does the Graceful Tree Conjecture (Ringel and Kotzig) say?
Every tree is graceful. Rosa showed that it implies Ringel's conjecture ( K2m+1K_{2m+1}K2m+1 decomposes into copies of any tree of size mmm ).
Graceful labelings were introduced by Alexander Rosa (as β-valuations); the name graceful is due to Golomb.
Rosa is credited with founding the subject of graph labelings.
Theorem 8.24 If TTT is a graceful tree of size mmm , then K2m+1K_{2m+1}K2m+1 is … ?
TTT -decomposable. The same holds for every graceful graph of size mmm .
Why does a graceful tree TTT of size mmm decompose K2m+1K_{2m+1}K2m+1 into copies of TTT ?
Put the vertex labelled iii at viv_ivi of a regular (2m+1)(2m+1)(2m+1) -gon: then TTT has exactly one edge of each length 1,…,m1, \dots, m1,…,m , and its 2m+12m + 12m+1 rotations use every edge of K2m+1K_{2m+1}K2m+1 once. K2m+1K_{2m+1}K2m+1 has exactly 2m+12m + 12m+1 edges of each length. This is a cyclic TTT -decomposition.
What is the goal of the Instant Insanity puzzle?
Stack four cubes, whose faces are red, blue, green or yellow, so that each of the four sides of the stack shows all four colors.
Up to turning the whole stack, in how many ways can four cubes be stacked?
3⋅243=41,472\boldsymbol{3 \cdot 24^3 = 41{,}472}3⋅243=41,472 The bottom cube matters only by which pair of opposite faces is buried (3 ways); each other cube can show any of 6 faces at the front, in 4 rotations.
In the graph solution of Instant Insanity, which pseudograph is built for each cube?
Vertices: the 4 colors. One edge c1c2c_1c_2c1c2 for each of the 3 pairs of opposite faces, colored c1c_1c1 and c2c_2c2 (a loop if c1=c2c_1 = c_2c1=c2 ). The four are combined into one pseudograph with 12 edges, each labelled by its cube's number.
Instant Insanity: four cubes with faces colored R, B, G, Y. For cube iii , join colors c1,c2c_1, c_2c1,c2 by an edge labelled iii for each pair of opposite faces colored c1,c2c_1, c_2c1,c2 (a loop if c1=c2c_1 = c_2c1=c2 ). The union of these edges is a pseudograph MMM on the 4 colors.What in MMM corresponds to a solution of the puzzle?
Two edge-disjoint 2-regular spanning sub-pseudographs of MMM , each with exactly one edge of each label 1, 2, 3, 4. One for front/back, one for left/right: each color appears once in front and once at the back, so has degree 2 (a loop counts 2).
Instant Insanity: four cubes with faces colored R, B, G, Y. For cube iii , join colors c1,c2c_1, c_2c1,c2 by an edge labelled iii for each pair of opposite faces colored c1,c2c_1, c_2c1,c2 (a loop if c1=c2c_1 = c_2c1=c2 ). The union of these edges is a pseudograph MMM on the 4 colors.Given the front/back and left/right sub-pseudographs, how do you place the cubes?
Orient each cycle as a directed cycle: an arc from c1c_1c1 to c2c_2c2 labelled iii means cube iii shows c1c_1c1 in front and c2c_2c2 at the back (and likewise right and left). e.g. arc (G, B) labelled 1 in the front/back graph: cube 1 has green in front and blue at the back.
Who designed the best-known version of Instant Insanity, and how well did it sell?
Frank Armbruster, 1965; over 12 million copies in 1966–1967. The puzzle goes back to 1900: Schossow's “The Great Tantalizer”, with playing-card suits on the faces.
Why is Julius Petersen's 1891 paper “Die Theorie der regulären graphs” important?
It is arguably the first paper of fundamental results on the theory of graphs. It contains Petersen's theorem (every 3-regular bridgeless graph has a 1-factor) and the 2-factorization theorem (2-factorable ⇔\Leftrightarrow⇔ rrr -regular, rrr even).
Where did Petersen introduce the Petersen graph, and why?
In an 1898 paper, as a counterexample to Tait's claim that every 3-regular bridgeless graph is 1-factorable. Petersen's own drawing. The graph had already appeared in an 1886 paper of Kempe.
The term graph in its present sense was first used by Sylvester, in 1878.
Petersen's use of the term made it spread. Sylvester and Petersen nearly co-authored Petersen's 1891 paper.
The Petersen graph consists of the 5-cycles (v1,…,v5,v1)(v_1, \dots, v_5, v_1)(v1,…,v5,v1) and (v1′,…,v5′,v1′)(v_1', \dots, v_5', v_1')(v1′,…,v5′,v1′) and a matching between them. Which matching?
v1v1′, v2v3′, v3v5′, v4v2′, v5v4′\boldsymbol{v_1v_1', \ v_2v_3', \ v_3v_5', \ v_4v_2', \ v_5v_4'}v1v1′, v2v3′, v3v5′, v4v2′, v5v4′ viv_ivi is joined to v2i−1′v'_{2i-1}v2i−1′ (indices mod 5): the outer cycle to the pentagram.
The length of a smallest cycle in a graph is its girth.
The Petersen graph has girth 5.
What is a ggg -cage ( g≥3g \ge 3g≥3 )?
A 3-regular graph of minimum order with girth ggg (shortest cycle of length ggg ).
What are the 3-cage, the 4-cage and the 5-cage?
K4\boldsymbol{K_4}K4 , K3,3\boldsymbol{K_{3,3}}K3,3 and the Petersen graph, each unique.
Why does every 3-regular graph of girth 5 have at least 10 vertices?
A vertex has 3 neighbors, each with 2 further neighbors, and these 1+3+61 + 3 + 61+3+6 vertices are distinct, since there are no triangles or 4-cycles.
A 5-cage (3-regular, girth 5, minimum order) has 10 vertices: v1v_1v1 , its neighbors v2,v3,v4v_2, v_3, v_4v2,v3,v4 , and their other neighbors v5,v6v_5, v_6v5,v6 (of v2v_2v2 ), v7,v8v_7, v_8v7,v8 (of v3v_3v3 ), v9,v10v_9, v_{10}v9,v10 (of v4v_4v4 ).Why must the 5-cage be the Petersen graph?
The remaining edges are forced up to symmetry, by excluding triangles and 4-cycles. e.g. v5v_5v5 is adjacent to exactly one of v7,v8v_7, v_8v7,v8 and one of v9,v10v_9, v_{10}v9,v10 ; say v7,v9v_7, v_9v7,v9 . Then v6∼v8,v10v_6 \sim v_8, v_{10}v6∼v8,v10 , then v7∼v10v_7 \sim v_{10}v7∼v10 and v8∼v9v_8 \sim v_9v8∼v9 .
What are the 6-cage, the 7-cage and the 8-cage called?
The Heawood graph, the McGee graph and the Tutte–Coxeter graph (each unique). Orders 14, 24 and 30.