Ch. 5: Connectivity

From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 5.1. Cut-Vertices 5.2. Blocks 5.3. Connectivity 5.4. Menger's Theorem 5.5. Exploration: Powers and Edge Labelings

77 flashcards · Mathematics · by lakesare

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

For a vertex vvv of a graph GGG and a proper subset UUU of V(G)V(G)V(G) , what are G−vG - vG−v and G−UG - UG−U ?
G−vG - vG−v : delete vvv and every edge incident with vvv . G−U\ G - U G−U : the subgraph induced by V(G)−UV(G) - UV(G)−U . Both are induced subgraphs of GGG .
When is a vertex vvv a cut-vertex of a graph GGG ?
When removing vvv disconnects its component: for connected GGG , when G−vG - vG−v is disconnected.
Which vertices of GGG are cut-vertices?
Only vvv and xxx . In G−vG - vG−v , xxx is no longer a cut-vertex, while sss now is one: so G−{s,v}G - \{s, v\}G−{s,v} is disconnected.
Theorem 5.1 Let vvv be a vertex incident with a bridge in a connected graph GGG . Then vvv is a cut-vertex of GGG if and only if … ?
deg⁡v≥2\boldsymbol{\deg v \ge 2}degv≥2 So in a nontrivial tree (where every edge is a bridge) the cut-vertices are exactly the vertices that are not end-vertices.
Let uvuvuv be a bridge (an edge on no cycle) of a connected graph GGG , with deg⁡v≥2\deg v \ge 2degv≥2 .Why is vvv a cut-vertex?
Otherwise a uuu – www path in G−vG - vG−v , for another neighbor www of vvv , together with the edges uvuvuv and vwvwvw forms a cycle containing the bridge uvuvuv . If instead deg⁡v=1\deg v = 1degv=1 , then vvv is an end-vertex and G−vG - vG−v stays connected.
Corollary 5.2 Let GGG be a connected graph of order 3 or more. If GGG contains a bridge, then … ?
GGG contains a cut-vertex. Order 3 is needed: K2K_2K2 has a bridge but no cut-vertex. The converse fails: three triangles sharing one vertex have a cut-vertex but no bridge.
Corollary 5.4 A vertex vvv of a connected graph GGG is a cut-vertex of GGG if and only if … ?
There are vertices uuu and www distinct from vvv such that vvv lies on every uuu – www path. If vvv is a cut-vertex, take u,wu, wu,w in different components of G−vG - vG−v : a uuu – www path avoiding vvv would lie in G−vG - vG−v . Conversely, such u,wu, wu,w are not connected in G−vG - vG−v .
Theorem 5.5 Let GGG be a nontrivial connected graph and u∈V(G)u \in V(G)u∈V(G) . If vvv is a vertex that is farthest from uuu in GGG , then … ?
vvv is not a cut-vertex of GGG .
GGG is a nontrivial connected graph and vvv is a vertex farthest from the vertex uuu .Why is vvv not a cut-vertex?
A vertex www in a component of G−vG - vG−v not containing uuu would satisfy d(u,w)>d(u,v)d(u, w) > d(u, v)d(u,w)>d(u,v) , since every uuu – www path passes through vvv .
Every edge of a connected graph can be a bridge. Can every vertex of a nontrivial connected graph be a cut-vertex?
No: every nontrivial connected graph has at least two vertices that are not cut-vertices. Take u,vu, vu,v with d(u,v)=diam⁡(G)d(u, v) = \operatorname{diam}(G)d(u,v)=diam(G) (the greatest distance in GGG ): each is farthest from the other, and a vertex farthest from some vertex is never a cut-vertex. (All edges are bridges exactly when GGG is a tree.)
A nontrivial connected graph with no cut-vertices is called nonseparable.
e.g. cycles and complete graphs. K2K_2K2 is the only nonseparable graph of order 2; one of order 3 or more has no bridges (a bridge would give a cut-vertex), so every edge lies on a cycle.
Theorem 5.7 A graph of order at least 3 is nonseparable if and only if … ?
Every two vertices lie on a common cycle.
GGG has order at least 3 and every two vertices of GGG lie on a common cycle.Why can't GGG have a cut-vertex vvv ?
For u,wu, wu,w in different components of G−vG - vG−v , their common cycle gives two uuu – www paths, and at most one of them contains vvv . But a cut-vertex vvv lies on every uuu – www path for such u,wu, wu,w .
GGG is nonseparable of order at least 3 (so every edge lies on a cycle).What is the key idea of the proof that every two vertices of GGG lie on a common cycle?
Take a pair u,vu, vu,v on no common cycle with d(u,v)=kd(u, v) = kd(u,v)=k as small as possible, and build a cycle through both anyway. k≥2k \ge 2k≥2 . Let vk−1v_{k-1}vk−1 precede vvv on a uuu – vvv geodesic: by minimality uuu and vk−1v_{k-1}vk−1 lie on a cycle CCC (not through vvv ). Since vk−1v_{k-1}vk−1 is not a cut-vertex, a vvv – uuu path QQQ avoids vk−1v_{k-1}vk−1 ; let xxx be its first vertex on CCC . Then go v→vk−1v \to v_{k-1}v→vk−1 , along CCC through uuu to xxx ( P′P'P′ ),…
What is a block of a graph GGG ?
A maximal nonseparable subgraph of GGG , i.e. one that is not a proper subgraph of another nonseparable subgraph. Each block is an induced subgraph. A nonseparable GGG is its own only block; a connected GGG with cut-vertices has two or more. Blocks are to a connected graph what components are to a disconnected one.
What are the blocks of GGG ?
Four blocks, joined at the cut-vertices uuu and vvv : B3B_3B3 is the bridge ux1ux_1ux1 , a block isomorphic to K2K_2K2 .
Theorem 5.8 On the edge set of a nontrivial connected graph GGG , let eRfe \mathrel{R} feRf if e=fe = fe=f or eee and fff lie on a common cycle. Then … ?
RRR is an equivalence relation. Each equivalence class induces a block of GGG , so this is a second way to describe the blocks.
Edges e,fe, fe,f lie on a cycle CCC , and f,gf, gf,g lie on a cycle C′C'C′ , with eee not on C′C'C′ and ggg not on CCC .How do you find a cycle containing eee and ggg ?
Follow CCC from the ends of e=uve = uve=uv until it meets C′C'C′ at xxx and yyy ; the xxx – yyy path on CCC through eee and the xxx – yyy path on C′C'C′ through ggg form the cycle. xxx , yyy : the first and last vertices on C′C'C′ of the uuu – vvv path on CCC that avoids eee . This is the transitivity of “on a common cycle”.
Corollary 5.9. Which three properties do two distinct blocks B1,B2B_1, B_2B1,B2 of a nontrivial connected graph GGG have?
(a) They are edge-disjoint. (b) They have at most one common vertex. (c) A common vertex is a cut-vertex of GGG .
Two edges lie in the same block exactly when they are equal or lie on a common cycle.Why can't two distinct blocks B1,B2B_1, B_2B1,B2 share two vertices u,vu, vu,v ?
A uuu – vvv path in B1B_1B1 and one in B2B_2B2 (edge-disjoint) would give a cycle containing an edge of each block. Follow both paths from uuu to their first common vertex www after uuu .
Two edges lie in the same block exactly when they are equal or lie on a common cycle.Two distinct blocks share a vertex vvv . Why is vvv a cut-vertex?
Otherwise a v1v_1v1 – v2v_2v2 path avoiding vvv , with vv1vv_1vv1 in one block and vv2vv_2vv2 in the other, closes a cycle containing both edges. If vvv is not a cut-vertex, every two other vertices are joined by a path avoiding vvv .
What is a vertex-cut of a graph GGG , and a minimum vertex-cut?
A set UUU of vertices with G−UG - UG−U disconnected; a minimum one has the smallest cardinality.
Which connected graphs have a vertex-cut?
Exactly those that are not complete. If u,vu, vu,v are nonadjacent, removing all other vertices leaves u,vu, vu,v disconnected. Removing vertices of a complete graph leaves a complete graph.
UUU is a minimum vertex-cut of a connected graph GGG , and G1,…,GkG_1, \dots, G_kG1,…,Gk are the components of G−UG - UG−U . Why is every u∈Uu \in Uu∈U adjacent to some vertex of each GiG_iGi ?
Otherwise U−{u}U - \{u\}U−{u} would already be a vertex-cut, contradicting minimality. No edges join different components GiG_iGi .
What is the connectivity (vertex-connectivity) κ(G)\kappa(G)κ(G) of a graph GGG ?
The minimum ∣U∣|U|∣U∣ over sets U⊆V(G)U \subseteq V(G)U⊆V(G) with G−UG - UG−U disconnected or trivial. For noncomplete GGG : the size of a minimum vertex-cut; κ(Kn)=n−1\kappa(K_n) = n - 1κ(Kn)=n−1 . For order nnn : 0≤κ(G)≤n−10 \le \kappa(G) \le n - 10≤κ(G)≤n−1 .
For a nontrivial graph GGG , when is κ(G)=0\kappa(G) = 0κ(G)=0 , when κ(G)=1\kappa(G) = 1κ(G)=1 , and when κ(G)≥2\kappa(G) \ge 2κ(G)≥2 ?
κ=0\kappa = 0κ=0 : disconnected. κ=1\ \kappa = 1 κ=1 : K2K_2K2 or connected with a cut-vertex. κ≥2\ \kappa \ge 2 κ≥2 : nonseparable of order ≥3\ge 3≥3 .
What is the connectivity κ\kappaκ of each of G1,…,G7G_1, \dots, G_7G1,…,G7 ?
1,1,1,2,2,4,6\boldsymbol{1, 1, 1, 2, 2, 4, 6}1,1,1,2,2,4,6 G1,G2,G3G_1, G_2, G_3G1,G2,G3 have cut-vertices, G4=C7G_4 = C_7G4=C7 , and G7=K7G_7 = K_7G7=K7 has κ=7−1\kappa = 7 - 1κ=7−1 .
When is a graph kkk -connected?
When κ(G)≥k\kappa(G) \ge kκ(G)≥k : removing fewer than kkk vertices never leaves a disconnected or trivial graph. A kkk -connected graph is ℓ\ellℓ -connected for 0≤ℓ≤k0 \le \ell \le k0≤ℓ≤k . 1-connected = nontrivial and connected; 2-connected = nonseparable of order ≥3\ge 3≥3 .
What is an edge-cut of a graph GGG , and when is it minimal, and when minimum?
A set XXX of edges with G−XG - XG−X disconnected. Minimal: no proper subset is an edge-cut. Minimum: smallest cardinality. Every minimum edge-cut is minimal, but not conversely.
XXX is a minimal edge-cut of a connected graph GGG . What does G−XG - XG−X look like?
Exactly two components G1,G2G_1, G_2G1,G2 , and XXX is the set of all edges joining them. With three or more components, putting back an edge of XXX that joins two of them leaves the graph disconnected, so XXX would not be minimal.
X1={e3,e4,e5}X_1 = \{e_3, e_4, e_5\}X1={e3,e4,e5} , X2={e1,e2,e6}X_2 = \{e_1, e_2, e_6\}X2={e1,e2,e6} and X3={e1,e6}X_3 = \{e_1, e_6\}X3={e1,e6} are edge-cuts of HHH . Which are minimal, and which are minimum?
Minimal: X1X_1X1 and X3X_3X3 . Minimum: only X3X_3X3 . X2X_2X2 is not minimal since X3⊂X2X_3 \subset X_2X3⊂X2 . No single edge disconnects HHH , so X3X_3X3 is minimum.
What is the edge-connectivity λ(G)\lambda(G)λ(G) of a graph GGG ?
The minimum ∣X∣|X|∣X∣ over sets X⊆E(G)X \subseteq E(G)X⊆E(G) with G−XG - XG−X disconnected or trivial. So λ(K1)=0\lambda(K_1) = 0λ(K1)=0 , and 0≤λ(G)≤n−10 \le \lambda(G) \le n - 10≤λ(G)≤n−1 for order nnn . λ(G)=0\lambda(G) = 0λ(G)=0 iff GGG is disconnected or trivial; λ(G)=1\lambda(G) = 1λ(G)=1 iff GGG is connected with a bridge.
When is a graph kkk -edge-connected, and what does 2-edge-connected mean?
λ(G)≥k\lambda(G) \ge kλ(G)≥k . 2-edge-connected: connected, of order ≥3\ge 3≥3 , with no bridges. 1-edge-connected = nontrivial and connected.
Theorem 5.10. For every positive integer nnn , λ(Kn)= ?\lambda(K_n) = \; ?λ(Kn)=? (edge-connectivity of the complete graph)
n−1\boldsymbol{n - 1}n−1 A minimum edge-cut splits KnK_nKn into parts of orders kkk and n−kn - kn−k and contains all k(n−k)k(n - k)k(n−k) edges between them, and k(n−k)−(n−1)=(k−1)(n−k−1)≥0k(n - k) - (n - 1) = (k - 1)(n - k - 1) \ge 0k(n−k)−(n−1)=(k−1)(n−k−1)≥0 .
Theorem 5.11. How are κ(G)\kappa(G)κ(G) , λ(G)\lambda(G)λ(G) and δ(G)\delta(G)δ(G) (connectivity, edge-connectivity, minimum degree) related for every graph GGG ?
κ(G)≤λ(G)≤δ(G)\boldsymbol{\kappa(G) \le \lambda(G) \le \delta(G)}κ(G)≤λ(G)≤δ(G) Due to Hassler Whitney. λ≤δ\lambda \le \deltaλ≤δ : the δ(G)\delta(G)δ(G) edges at a vertex of minimum degree form an edge-cut.
GGG is connected, not complete, of order nnn ; XXX is a minimum edge-cut and G−XG - XG−X has components G1G_1G1 (order kkk ) and G2G_2G2 (order n−kn - kn−k ).Why must some u∈G1u \in G_1u∈G1 and v∈G2v \in G_2v∈G2 be nonadjacent?
Otherwise ∣X∣=k(n−k)≥n−1|X| = k(n - k) \ge n - 1∣X∣=k(n−k)≥n−1 , but ∣X∣=λ(G)≤δ(G)≤n−2|X| = \lambda(G) \le \delta(G) \le n - 2∣X∣=λ(G)≤δ(G)≤n−2 .
XXX is a minimum edge-cut of GGG , G−XG - XG−X has components G1,G2G_1, G_2G1,G2 , and u∈G1u \in G_1u∈G1 , v∈G2v \in G_2v∈G2 are nonadjacent.How does the proof of κ(G)≤λ(G)\kappa(G) \le \lambda(G)κ(G)≤λ(G) get a vertex-cut UUU with ∣U∣≤∣X∣|U| \le |X|∣U∣≤∣X∣ ?
From each edge of XXX take one end: the end in G2G_2G2 if the edge is incident with uuu , otherwise the end in G1G_1G1 . Then u,v∉Uu, v \notin Uu,v∈/U , and UUU meets every uuu – vvv path, so κ(G)≤∣U∣≤∣X∣=λ(G)\kappa(G) \le |U| \le |X| = \lambda(G)κ(G)≤∣U∣≤∣X∣=λ(G) .
Hassler Whitney, who proved κ(G)≤λ(G)≤δ(G)\kappa(G) \le \lambda(G) \le \delta(G)κ(G)≤λ(G)≤δ(G) , was primarily interested in which field?
Topology. He still made major contributions to graph theory: his Harvard dissertation (1932, under Birkhoff) was in graph theory.
Can both inequalities in κ(G)≤λ(G)≤δ(G)\kappa(G) \le \lambda(G) \le \delta(G)κ(G)≤λ(G)≤δ(G) be strict at once?
Yes, e.g. κ(G)=1\kappa(G) = 1κ(G)=1 , λ(G)=2\lambda(G) = 2λ(G)=2 , δ(G)=3\delta(G) = 3δ(G)=3 :
Theorem 5.12. For a cubic (3-regular) graph GGG , how are κ(G)\kappa(G)κ(G) and λ(G)\lambda(G)λ(G) related?
κ(G)=λ(G)\boldsymbol{\kappa(G) = \lambda(G)}κ(G)=λ(G)
A cubic graph GGG has a cut-vertex uuu . Why does GGG have a bridge?
The 3 neighbors of uuu lie in at least 2 components of G−uG - uG−u , so some component holds exactly one neighbor www ; then uwuwuw is a bridge.
GGG is cubic and U={u,v}U = \{u, v\}U={u,v} is a minimum vertex-cut, so each of u,vu, vu,v has neighbors in both components G1,G2G_1, G_2G1,G2 of G−UG - UG−U , and exactly one neighbor ( u′u'u′ , resp. v′v'v′ ) in one of them.Why is λ(G)=2\lambda(G) = 2λ(G)=2 ?
{uu′,vv′}\{uu', vv'\}{uu′,vv′} is an edge-cut. If u′,v′u', v'u′,v′ are in the same component, it cuts that component off (a). Otherwise uuu has 2 neighbors in G2G_2G2 and vvv has 2 in G1G_1G1 , so uvuvuv is not an edge and the cut separates G1G_1G1 and vvv from G2G_2G2 and uuu (b).
Theorem 5.13 If GGG is a graph of order nnn and size m≥n−1m \ge n - 1m≥n−1 , then κ(G)≤ ?\kappa(G) \le \; ?κ(G)≤?
⌊2mn⌋\boldsymbol{\left\lfloor \frac{2m}{n} \right\rfloor}⌊n2m⌋ δ(G)\delta(G)δ(G) is at most the average degree 2mn\frac{2m}{n}n2m , and κ(G)≤δ(G)\kappa(G) \le \delta(G)κ(G)≤δ(G) . (If m<n−1m < n - 1m<n−1 , GGG is disconnected and κ(G)=0\kappa(G) = 0κ(G)=0 .)
For a graph of order nnn and size m≥n−1m \ge n - 1m≥n−1 : κ(G)≤⌊2m/n⌋\kappa(G) \le \lfloor 2m/n \rfloorκ(G)≤⌊2m/n⌋ .Is this bound sharp? Which graphs attain it when m=n−1m = n - 1m=n−1 ?
Sharp for every n−1≤m≤(n2)n - 1 \le m \le \binom{n}{2}n−1≤m≤(2n) . For m=n−1m = n - 1m=n−1 : every tree. κ(T)=1=⌊(2n−2)/n⌋\kappa(T) = 1 = \lfloor (2n - 2)/n \rfloorκ(T)=1=⌊(2n−2)/n⌋ . The Harary graphs Hr,nH_{r,n}Hr,n attain it with κ=r\kappa = rκ=r .
GGG is connected of diameter ddd and 1≤k≤d1 \le k \le d1≤k≤d . What is the kkk th power GkG^kGk ?
Same vertices as GGG ; uvuvuv is an edge of GkG^kGk if 1≤dG(u,v)≤k1 \le d_G(u, v) \le k1≤dG(u,v)≤k .
The second power G2G^2G2 of a graph is its square, and the third power G3G^3G3 is its cube.
Theorem 5.14. If GGG is a connected graph of order at least 3, then its square G2G^2G2 is … ?
2-connected. More generally, GkG^kGk is kkk -connected for 2≤k<n2 \le k < n2≤k<n , where nnn is the order of GGG .
How is the Harary graph Hr,nH_{r,n}Hr,n ( 2≤r<n2 \le r < n2≤r<n ) defined when r=2kr = 2kr=2k is even?
Hr,n=CkH_{r,n} = C^kHr,n=Ck , the kkk th power of the nnn -cycle C=(v1,…,vn,v1)C = (v_1, \dots, v_n, v_1)C=(v1,…,vn,v1) . So it is rrr -regular of order nnn . H4,8=C82H_{4,8} = C_8^2H4,8=C82 :
How is the Harary graph Hr,nH_{r,n}Hr,n defined when r=2k+1r = 2k + 1r=2k+1 is odd and n=2ℓn = 2\elln=2ℓ is even?
CkC^kCk (the kkk th power of the nnn -cycle (v1,…,vn,v1)(v_1, \dots, v_n, v_1)(v1,…,vn,v1) ) plus the edges vivi+ℓv_iv_{i+\ell}vivi+ℓ for 1≤i≤ℓ1 \le i \le \ell1≤i≤ℓ . Each vertex is also joined to the opposite one, so Hr,nH_{r,n}Hr,n is rrr -regular. H5,8H_{5,8}H5,8 :
How is the Harary graph Hr,nH_{r,n}Hr,n defined when r=2k+1r = 2k + 1r=2k+1 and n=2ℓ+1n = 2\ell + 1n=2ℓ+1 are both odd?
CkC^kCk (the kkk th power of the nnn -cycle (v1,…,vn,v1)(v_1, \dots, v_n, v_1)(v1,…,vn,v1) ) plus the edges vivi+ℓ+1v_iv_{i+\ell+1}vivi+ℓ+1 for 1≤i≤ℓ1 \le i \le \ell1≤i≤ℓ and the edge v1v1+ℓv_1v_{1+\ell}v1v1+ℓ . So n−1n - 1n−1 vertices have degree rrr and v1v_1v1 has degree r+1r + 1r+1 . H5,9H_{5,9}H5,9 :
Theorem 5.15. For integers 2≤r<n2 \le r < n2≤r<n , κ(Hr,n)= ?\kappa(H_{r,n}) = \; ?κ(Hr,n)=? ( Hr,nH_{r,n}Hr,n the Harary graph)
r\boldsymbol{r}r The easy half: δ(Hr,n)=r\delta(H_{r,n}) = rδ(Hr,n)=r , so κ≤r\kappa \le rκ≤r . Its size mmm is rn2\frac{rn}{2}2rn or rn+12\frac{rn+1}{2}2rn+1 , so ⌊2m/n⌋=r\lfloor 2m/n \rfloor = r⌊2m/n⌋=r : the Harary graphs show that κ(G)≤⌊2m/n⌋\kappa(G) \le \lfloor 2m/n \rfloorκ(G)≤⌊2m/n⌋ is sharp.
When does a set SSS of vertices of GGG separate two vertices uuu and vvv ?
When G−SG - SG−S is disconnected with uuu and vvv in different components. SSS is then a uuu – vvv separating set; one of minimum cardinality is a minimum uuu – vvv separating set. Such u,vu, vu,v are nonadjacent, and ∣S∣≥κ(G)|S| \ge \kappa(G)∣S∣≥κ(G) .
When is a collection of uuu – vvv paths internally disjoint?
When no two of the paths have a vertex in common other than uuu and vvv . An internal vertex of a uuu – vvv path is a vertex of it other than uuu and vvv .
Menger's Theorem (Theorem 5.16) Let uuu and vvv be nonadjacent vertices in a graph GGG . The minimum number of vertices in a uuu – vvv separating set equals … ?
The maximum number of internally disjoint uuu – vvv paths in GGG . U={w1,w2,w3}U = \{w_1, w_2, w_3\}U={w1,w2,w3} is a minimum uuu – vvv separating set; in bold, three internally disjoint uuu – vvv paths.
A minimum uuu – vvv separating set SSS of GGG has kkk vertices.Why are there at most kkk internally disjoint uuu – vvv paths?
Each uuu – vvv path contains a vertex of SSS , and internally disjoint paths can't share one. This is the easy half of Menger's Theorem.
Menger's Theorem is proved by induction on the size (number of edges). Case 1: a minimum uuu – vvv separating set UUU , ∣U∣=k|U| = k∣U∣=k , contains a vertex xxx adjacent to both uuu and vvv .How do you get kkk internally disjoint uuu – vvv paths?
In G−xG - xG−x , U−{x}U - \{x\}U−{x} is a minimum uuu – vvv separating set, so induction gives k−1k - 1k−1 paths; add the path (u,x,v)(u, x, v)(u,x,v) .
Menger's Theorem, proved by induction on the size. Case 2: a minimum uuu – vvv separating set W={w1,…,wk}W = \{w_1, \dots, w_k\}W={w1,…,wk} has a vertex not adjacent to uuu and a vertex not adjacent to vvv .What is the key idea?
Split GGG at WWW into a uuu -side and a vvv -side, find kkk paths from uuu to WWW and kkk paths from WWW to vvv by induction, and glue them at the wiw_iwi . GuG_uGu consists of the uuu – wiw_iwi paths meeting WWW only in wiw_iwi ; Gu′G_u'Gu′ adds a new vertex v′v'v′ joined to every wiw_iwi (likewise GvG_vGv , Gv′G_v'Gv′ with u′u'u′ ). Both have fewer edges than GGG , and GuG_uGu , GvG_vGv share only WWW .
Menger's Theorem, proved by induction on the size. Case 3: every minimum uuu – vvv separating set ( kkk vertices) is either entirely adjacent to uuu and not to vvv , or entirely adjacent to vvv and not to uuu .What is the key idea?
Delete the edge xyxyxy of a uuu – vvv geodesic (u,x,y,…,v)(u, x, y, \dots, v)(u,x,y,…,v) : uuu and vvv still need kkk vertices to be separated, so induction applies to G−xyG - xyG−xy . A smaller separating set ZZZ in G−xyG - xyG−xy would make Z∪{x}Z \cup \{x\}Z∪{x} and Z∪{y}Z \cup \{y\}Z∪{y} minimum separating sets of GGG . The first forces ZZZ to be adjacent to uuu , then the second forces yyy adjacent to uuu , contradicting the geodesic.
How did Menger's Theorem become widely known among graph theorists?
Dénes König added a final section on it to his book on graph theory, after Menger told him about it in Budapest in 1930. König didn't believe it and spent the night trying to build a counterexample (“A sleepless night!”). Menger had published it in 1927 as a lemma in curve theory, calling it the “ nnn -arc theorem”.
Whitney's Theorem (Theorem 5.17) A nontrivial graph GGG is kkk -connected, for k≥2k \ge 2k≥2 , if and only if … ?
For every two distinct vertices u,vu, vu,v there are at least kkk internally disjoint uuu – vvv paths. So κ(G)\kappa(G)κ(G) is also the largest kkk for which every two vertices are joined by kkk internally disjoint paths.
GGG is kkk -connected ( k≥2k \ge 2k≥2 ), and u,vu, vu,v are adjacent vertices.Why are there kkk internally disjoint uuu – vvv paths?
G−uvG - uvG−uv is (k−1)(k - 1)(k−1) -connected, so Menger's Theorem gives k−1k - 1k−1 internally disjoint uuu – vvv paths in G−uvG - uvG−uv ; the edge uvuvuv is the kkk th. For nonadjacent u,vu, vu,v , Menger's Theorem applies directly: a uuu – vvv separating set has at least κ(G)≥k\kappa(G) \ge kκ(G)≥k vertices.
Every two distinct vertices of a noncomplete graph GGG are joined by at least kkk internally disjoint paths.Why is GGG kkk -connected?
A minimum vertex-cut UUU separates two vertices x,yx, yx,y , so by Menger's Theorem ∣U∣≥|U| \ge∣U∣≥ the number of internally disjoint xxx – yyy paths ≥k\ge k≥k .
Theorem 5.18 Let GGG be a kkk -connected graph and SSS any set of kkk vertices. If HHH is obtained from GGG by adding a new vertex www joined to the vertices of SSS , then … ?
HHH is also kkk -connected.
For distinct vertices u,v1,…,vku, v_1, \dots, v_ku,v1,…,vk , when are uuu – viv_ivi paths P1,…,PkP_1, \dots, P_kP1,…,Pk internally disjoint? For distinct u1,…,uk,v1,…,vku_1, \dots, u_k, v_1, \dots, v_ku1,…,uk,v1,…,vk , when are uiu_iui – viv_ivi paths disjoint?
Internally disjoint: every two have only uuu in common. Disjoint: no two have a vertex in common.
Corollary 5.19 If GGG is kkk -connected and u,v1,…,vku, v_1, \dots, v_ku,v1,…,vk are k+1k + 1k+1 distinct vertices of GGG , then … ?
There are internally disjoint uuu – viv_ivi paths, 1≤i≤k1 \le i \le k1≤i≤k . Proof idea: add a new vertex www joined to v1,…,vkv_1, \dots, v_kv1,…,vk ; the result is still kkk -connected, so there are kkk internally disjoint uuu – www paths. Drop www .
Dirac's Theorem (Theorem 5.20). If GGG is kkk -connected, k≥2k \ge 2k≥2 , then … ?
Every kkk vertices of GGG lie on a common cycle. For k=2k = 2k=2 this is: in a nonseparable graph of order ≥3\ge 3≥3 , every two vertices lie on a common cycle.
GGG is kkk -connected, k≥2k \ge 2k≥2 , and SSS is a set of kkk vertices.What is the key idea of the proof that some cycle contains all of SSS ?
Take a cycle CCC through the maximum number ℓ\ellℓ of vertices of SSS ; if ℓ<k\ell < kℓ<k , reroute CCC through a missing u∈Su \in Su∈S along internally disjoint paths from uuu to CCC . If CCC has no vertices outside SSS , replace the edge v1v2v_1v_2v1v2 by paths uuu – v1v_1v1 and uuu – v2v_2v2 . Otherwise take ℓ+1\ell + 1ℓ+1 internally disjoint paths from uuu to CCC : two of them end on a stretch of CCC with no vertex of SSS inside, and replacing that stretch keeps all ℓ\ellℓ vertices and…
Theorem 5.21 (edge form of Menger's Theorem). For distinct vertices u,vu, vu,v of GGG , the minimum number of edges separating uuu and vvv equals … ?
The maximum number of pairwise edge-disjoint uuu – vvv paths.
Theorem 5.22. A nontrivial graph GGG is kkk -edge-connected if and only if … ?
Every two distinct vertices u,vu, vu,v are joined by kkk pairwise edge-disjoint uuu – vvv paths.
What is the distance-labeled graph GkG^kGk of a connected graph GGG , and when is a path in it proper?
Each edge uvuvuv of GkG^kGk is labeled dG(u,v)d_G(u, v)dG(u,v) . A path is proper if every two adjacent edges on it have different labels. In G2G^2G2 : edges of GGG get label 1, the others label 2.
GGG is connected of diameter ≥2\ge 2≥2 , and u,vu, vu,v are vertices. What is known about proper uuu – vvv paths in the distance-labeled G2G^2G2 (edges of GGG labeled 1, the others 2)?
There is always a proper uuu – vvv path, but not necessarily two internally disjoint ones. G2G^2G2 itself (order ≥3\ge 3≥3 ) is 2-connected, so it does have two internally disjoint uuu – vvv paths.
In the distance-labeled GkG^kGk (edge uvuvuv labeled dG(u,v)d_G(u, v)dG(u,v) ), why is an edge labeled j>1j > 1j>1 adjacent to an edge labeled iii for every i<ji < ji<j ?
If uvuvuv has label jjj , the vertex www at distance iii from uuu on a uuu – vvv geodesic gives an edge uwuwuw labeled iii . This property motivates Grundy labelings.
What is a proper edge labeling of a connected graph GGG ?
A labeling of the edges from {1,2,…,k}\{1, 2, \dots, k\}{1,2,…,k} in which no two adjacent edges get the same label.
What is a Grundy labeling of a tree TTT , and its Grundy index Γ′(T)\Gamma'(T)Γ′(T) ?
A proper edge labeling from {1,…,k}\{1, \dots, k\}{1,…,k} where every edge labeled j>1j > 1j>1 is adjacent to edges labeled iii for all i<ji < ji<j . Γ′(T)\Gamma'(T)Γ′(T) : the largest such kkk . Γ′(T)=4\Gamma'(T) = 4Γ′(T)=4 . Named for Patrick Michael Grundy, who worked on combinatorial games.
What are the bounds on the Grundy index Γ′(T)\Gamma'(T)Γ′(T) of a tree TTT in terms of Δ(T)\Delta(T)Δ(T) (the maximum degree)?
Δ(T)≤Γ′(T)≤2Δ(T)−1\boldsymbol{\Delta(T) \le \Gamma'(T) \le 2\Delta(T) - 1}Δ(T)≤Γ′(T)≤2Δ(T)−1 Upper bound: an edge labeled kkk needs k−1k - 1k−1 adjacent edges, and an edge has at most 2(Δ−1)2(\Delta - 1)2(Δ−1) .
What is an achromatic edge labeling of a tree TTT , and its achromatic index ψ′(T)\psi'(T)ψ′(T) ?
A proper edge labeling from {1,…,k}\{1, \dots, k\}{1,…,k} where every two distinct labels i,ji, ji,j occur on some pair of adjacent edges. ψ′(T)\psi'(T)ψ′(T) : the largest such kkk . ψ′(P9)=4\psi'(P_9) = 4ψ′(P9)=4 .
Why does the path P9P_9P9 (9 vertices) have no achromatic edge labeling with 5 labels?
P9P_9P9 has only 7 pairs of adjacent edges, but 5 labels form (52)=10\binom{5}{2} = 10(25)=10 pairs that must each occur. With 4 labels, (42)=6≤7\binom{4}{2} = 6 \le 7(24)=6≤7 , and 1,2,3,4,1,3,2,41, 2, 3, 4, 1, 3, 2, 41,2,3,4,1,3,2,4 works, so ψ′(P9)=4\psi'(P_9) = 4ψ′(P9)=4 .