Ch. 6: Traversability

From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 6.1. Eulerian Graphs 6.2. Hamiltonian Graphs 6.3. Exploration: Hamiltonian Walks 6.4. Excursion: Early Books of Graph Theory

66 flashcards · Mathematics · by lakesare

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

What is an Eulerian circuit in a graph GGG ?
A circuit that contains every edge of GGG . A circuit repeats no edge, so every edge appears exactly once. (v1,v2,v3,v4,v5,v6,v7,v2,v4,v7,v8,v6,v9,v8,v11,v9,v10,v11,v1)(v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_2, v_4, v_7, v_8, v_6, v_9, v_8, v_{11}, v_9, v_{10}, v_{11}, v_1)(v1,v2,v3,v4,v5,v6,v7,v2,v4,v7,v8,v6,v9,v8,v11,v9,v10,v11,v1) is an Eulerian circuit: a letter carrier's round trip passing every street once.
What is an Eulerian graph?
A connected graph that contains an Eulerian circuit. Connectedness costs nothing: only a graph with a single nontrivial component can contain an Eulerian circuit.
What is an Eulerian trail in a connected graph GGG ?
An open trail that contains every edge of GGG . (u,s,t,u,v,w,y,u,w,x,z,w)(u, s, t, u, v, w, y, u, w, x, z, w)(u,s,t,u,v,w,y,u,w,x,z,w) is an Eulerian trail.
What was the Königsberg Bridge Problem?
Can one take a walk in Königsberg that crosses each of its seven bridges exactly once? The river Pregel split the city into four land areas A, B, C, D. The problem reached Euler.
The Königsberg multigraph: land areas as vertices, the seven bridges as edges. Why is there no walk crossing every bridge exactly once?
All four vertices have odd degree, yet every vertex that is neither the start nor the end of such a walk would need even degree. The walk would be a trail of length 7 through 8 vertex visits, so at least two land areas are neither initial nor terminal. Each visit to such a vertex enters and leaves it, using 2 edges.
Theorem 6.1 (Euler) A nontrivial connected graph GGG is Eulerian if and only if … ?
Every vertex of GGG has even degree. The same holds for multigraphs.
Why does every vertex of an Eulerian graph have even degree?
Each time the Eulerian circuit passes through a vertex, it uses 2 of its edges (one in, one out). At the start vertex uuu the first and the last edge of the circuit also pair up.
To show: a nontrivial connected graph GGG in which every vertex has even degree is Eulerian. Let TTT be a trail of maximum length in GGG , say a uuu – vvv trail.Why must TTT be closed ( u=vu = vu=v )?
If TTT ended at v≠uv \ne uv=u , it would use an odd number of edges at vvv , so some edge vwvwvw at vvv is unused and TTT could be extended. Every earlier visit of TTT to vvv uses 2 edges, and the end adds 1; since deg⁡v\deg vdegv is even, an edge remains.
To show: a nontrivial connected graph GGG in which every vertex has even degree is Eulerian. A trail of maximum length is a circuit CCC .Why does CCC contain every edge of GGG ?
Otherwise splice in a second circuit at a vertex xxx of CCC , giving a longer circuit. GGG is connected, so some unused edge xyxyxy has xxx on CCC . In H=G−E(C)H = G - E(C)H=G−E(C) every degree is even, so a longest trail from xxx in the component of HHH containing xyxyxy is an xxx – xxx circuit C′C'C′ . Inserting C′C'C′ into CCC at xxx contradicts the maximality of CCC .
Who completed the proof that a connected graph whose vertices all have even degree is Eulerian, and when?
Carl Hierholzer, published in 1873. Euler had only shown the other direction. Hierholzer had died by then; a colleague wrote up the paper with Hierholzer as sole author.
Corollary 6.2 A connected graph GGG contains an Eulerian trail if and only if … ? And where does each Eulerian trail start and end?
Exactly two vertices of GGG have odd degree, and each Eulerian trail starts at one of them and ends at the other.
A connected graph contains an Eulerian trail if and only if exactly two of its vertices, uuu and vvv , have odd degree.How does the proof reduce this to the characterization of Eulerian graphs (all degrees even)?
Add a new vertex xxx joined to uuu and vvv . Now all degrees are even. An Eulerian circuit of the new graph runs through uxuxux and xvxvxv consecutively; deleting xxx leaves a uuu – vvv Eulerian trail of GGG , and conversely a uuu – vvv Eulerian trail plus v,x,uv, x, uv,x,u is an Eulerian circuit.
For which nnn is the complete graph KnK_nKn Eulerian, and for which s,ts, ts,t is Ks,tK_{s,t}Ks,t ?
KnK_nKn : n≥3n \ge 3n≥3 odd. Ks,t\ K_{s,t} Ks,t : sss and ttt both even. KnK_nKn is (n−1)(n-1)(n−1) -regular; in Ks,tK_{s,t}Ks,t the degrees are sss and ttt .
For which nnn is the nnn -cube QnQ_nQn Eulerian, and for which ttt does K2,tK_{2,t}K2,t have an Eulerian trail?
QnQ_nQn : n≥2n \ge 2n≥2 even. K2,t\ K_{2,t} K2,t : ttt odd. QnQ_nQn is nnn -regular. K2,tK_{2,t}K2,t has two vertices of degree ttt and ttt of degree 2, so exactly two odd vertices when ttt is odd.
The Cartesian product G×HG \times HG×H replaces each vertex vvv of GGG by a copy HvH_vHv of HHH . For a vertex xxx of HvH_vHv , what is deg⁡G×Hx\deg_{G \times H} xdegG×Hx ?
deg⁡G×Hx=deg⁡Hvx+deg⁡Gv\boldsymbol{\deg_{G \times H} x = \deg_{H_v} x + \deg_G v}degG×Hx=degHvx+degGv xxx keeps its neighbors in HvH_vHv and gains one neighbor in HuH_uHu for each neighbor uuu of vvv in GGG .
GGG and HHH are nontrivial connected graphs. When is the Cartesian product G×HG \times HG×H Eulerian?
When GGG and HHH are both Eulerian, or every vertex of GGG and of HHH has odd degree. deg⁡G×Hx=deg⁡Hx+deg⁡Gv\deg_{G \times H} x = \deg_H x + \deg_G vdegG×Hx=degHx+degGv is even exactly when the two degrees have the same parity, and this must hold for every vertex xxx of HHH and vvv of GGG .
For nontrivial connected GGG and HHH : G×HG \times HG×H is Eulerian if and only if both are Eulerian or every vertex of GGG and of HHH has odd degree.Is K4×K2K_4 \times K_2K4×K2 Eulerian? Is the 3-cube Q3=Q2×K2Q_3 = Q_2 \times K_2Q3=Q2×K2 ?
K4×K2K_4 \times K_2K4×K2 : yes. Q3\ Q_3 Q3 : no. K4K_4K4 (3-regular) and K2K_2K2 have only odd vertices, so K4×K2K_4 \times K_2K4×K2 is 4-regular. Q2=C4Q_2 = C_4Q2=C4 is Eulerian but K2K_2K2 is not, and Q3Q_3Q3 is 3-regular.
Who convinced Euler's father to let Euler study mathematics instead of theology, and later became Euler's advisor?
Johann Bernoulli. So Bernoulli is Euler's "academic father". Euler, born in Basel in 1707, did much of his later research while totally blind.
What is a Hamiltonian cycle of a graph GGG , and what is a Hamiltonian graph?
A cycle that contains every vertex of GGG (a spanning cycle). A Hamiltonian graph contains a Hamiltonian cycle. e.g. CnC_nCn ( n≥3n \ge 3n≥3 ) and KnK_nKn ( n≥3n \ge 3n≥3 ). A museum's rooms and doorways: the cycle (R1, R2, R4, R9, R13, R14, R10, R5, R6, R7, R11, R15, R12, R8, R3, R1) visits each room once.
What is a Hamiltonian path in a graph GGG ? How does having one relate to being Hamiltonian?
A path containing every vertex of GGG . A Hamiltonian graph has one, but not conversely. Delete any edge of a Hamiltonian cycle to get a Hamiltonian path. PnP_nPn has a Hamiltonian path and no cycle at all.
What does a Hamiltonian graph of order nnn look like?
A cycle of length nnn , possibly with extra edges joining nonconsecutive vertices of the cycle. K3,3K_{3,3}K3,3 redrawn around the Hamiltonian cycle (u,x,v,y,w,z,u)(u, x, v, y, w, z, u)(u,x,v,y,w,z,u) .
GGG is a 3-regular Hamiltonian graph. How many of the three edges at each vertex does a Hamiltonian cycle use?
Exactly two (it misses exactly one). A Hamiltonian cycle is a 2-regular spanning subgraph.
vvv is a vertex of degree 2 in a graph GGG . What can you say about the Hamiltonian cycles of GGG ?
Both edges at vvv lie on every Hamiltonian cycle. A Hamiltonian cycle uses exactly 2 edges at every vertex. Together with "no vertex may get 3 cycle edges" this is the standard way to prove a graph non-Hamiltonian.
Why is this graph not Hamiltonian?
The degree-2 vertices ttt , xxx , vvv force tztztz , xzxzxz , vzvzvz onto any Hamiltonian cycle, giving zzz three cycle edges. Both edges at a degree-2 vertex lie on every Hamiltonian cycle: tu,tztu, tztu,tz ; xy,xzxy, xzxy,xz ; vw,vzvw, vzvw,vz .
Theorem 6.4. Is the Petersen graph Hamiltonian?
No. 3-regular of order 10: outer 5-cycle C′=(u1,…,u5,u1)C' = (u_1, \dots, u_5, u_1)C′=(u1,…,u5,u1) , inner 5-cycle C′′=(v1,v3,v5,v2,v4,v1)C'' = (v_1, v_3, v_5, v_2, v_4, v_1)C′′=(v1,v3,v5,v2,v4,v1) and the spokes uiviu_iv_iuivi . Its shortest cycles have length 5.
Petersen graph: outer 5-cycle C′=(u1,…,u5,u1)C' = (u_1, \dots, u_5, u_1)C′=(u1,…,u5,u1) , inner 5-cycle C′′=(v1,v3,v5,v2,v4,v1)C'' = (v_1, v_3, v_5, v_2, v_4, v_1)C′′=(v1,v3,v5,v2,v4,v1) , spokes uiviu_iv_iuivi . Suppose CCC is a Hamiltonian cycle.Why may we assume that CCC contains 3 or 4 edges of C′C'C′ ?
CCC has 10 edges and at most 5 are spokes, so C′C'C′ or C′′C''C′′ (say C′C'C′ ) contains at least 3 edges of CCC ; all 5 is impossible. If CCC contained all of C′C'C′ , the cycle CCC would contain the smaller cycle C′C'C′ . Renaming makes either 5-cycle the outer one.
Petersen graph: outer 5-cycle C′=(u1,…,u5,u1)C' = (u_1, \dots, u_5, u_1)C′=(u1,…,u5,u1) , inner 5-cycle C′′=(v1,v3,v5,v2,v4,v1)C'' = (v_1, v_3, v_5, v_2, v_4, v_1)C′′=(v1,v3,v5,v2,v4,v1) , spokes uiviu_iv_iuivi . A Hamiltonian cycle CCC contains exactly the edges u4u5,u5u1,u1u2,u2u3u_4u_5, u_5u_1, u_1u_2, u_2u_3u4u5,u5u1,u1u2,u2u3 of C′C'C′ .Why is that impossible?
The forced edges close an 8-cycle (u4,u5,u1,u2,u3,v3,v1,v4,u4)(u_4, u_5, u_1, u_2, u_3, v_3, v_1, v_4, u_4)(u4,u5,u1,u2,u3,v3,v1,v4,u4) inside CCC . u1,u2,u5u_1, u_2, u_5u1,u2,u5 already have 2 cycle edges, so u1v1,u2v2,u5v5u_1v_1, u_2v_2, u_5v_5u1v1,u2v2,u5v5 are out; then u3v3,u4v4u_3v_3, u_4v_4u3v3,u4v4 are forced, and v1v_1v1 must use v1v3,v1v4v_1v_3, v_1v_4v1v3,v1v4 . Dashed: edges that cannot be on CCC .
Petersen graph: outer 5-cycle C′=(u1,…,u5,u1)C' = (u_1, \dots, u_5, u_1)C′=(u1,…,u5,u1) , inner 5-cycle C′′=(v1,v3,v5,v2,v4,v1)C'' = (v_1, v_3, v_5, v_2, v_4, v_1)C′′=(v1,v3,v5,v2,v4,v1) , spokes uiviu_iv_iuivi . A Hamiltonian cycle CCC contains exactly 3 edges of C′C'C′ .Why is that impossible, both when the 3 edges are consecutive on C′C'C′ and when they aren't?
Consecutive ( u5u4,u4u3,u3u2u_5u_4, u_4u_3, u_3u_2u5u4,u4u3,u3u2 ): u1u_1u1 is left with only u1v1u_1v_1u1v1 . Not consecutive ( u5u1,u1u2,u4u3u_5u_1, u_1u_2, u_4u_3u5u1,u1u2,u4u3 ): CCC would contain the 5-cycle (u4,v4,v1,v3,u3,u4)(u_4, v_4, v_1, v_3, u_3, u_4)(u4,v4,v1,v3,u3,u4) . Dashed: edges that cannot be on CCC .
What was Hamilton's Icosian Game (1857)?
Find a round trip through the 20 corners ("cities") of a regular dodecahedron, visiting each exactly once, i.e. a Hamiltonian cycle of the dodecahedron graph. A commercial failure, sold to J. Jaques and Sons. About two years earlier Thomas Kirkman had already asked about such cycles in polyhedra, so Hamilton wasn't the first.
Why is every Hamiltonian graph 2-connected (connected, order ≥3\ge 3≥3 , no cut-vertex)?
Deleting one vertex from a Hamiltonian cycle leaves a path through all remaining vertices, so G−vG - vG−v stays connected.
Theorem 6.5. GGG is a Hamiltonian graph and k(H)k(H)k(H) is the number of components of a graph HHH . Then for every nonempty proper subset SSS of V(G)V(G)V(G) , k(G−S)≤ ?\; k(G - S) \le \; ?k(G−S)≤?
k(G−S)≤∣S∣\boldsymbol{k(G - S) \le |S|}k(G−S)≤∣S∣
GGG is Hamiltonian, SSS is a nonempty proper subset of V(G)V(G)V(G) , and G−SG - SG−S has components G1,…,GkG_1, \dots, G_kG1,…,Gk .Why is k≤∣S∣k \le |S|k≤∣S∣ ?
Each time a Hamiltonian cycle leaves some GiG_iGi for the last time, its next vertex lies in SSS , and these are kkk different vertices of SSS .
Why is this graph not Hamiltonian?
Removing S={u,v,w}S = \{u, v, w\}S={u,v,w} leaves 4 components, and 4>3=∣S∣4 > 3 = |S|4>3=∣S∣ . A Hamiltonian graph has k(G−S)≤∣S∣k(G - S) \le |S|k(G−S)≤∣S∣ for every nonempty proper S⊂V(G)S \subset V(G)S⊂V(G) ( kkk = number of components). With S={v}S = \{v\}S={v} : a graph with a cut-vertex isn't Hamiltonian.
GGG is a graph with k(G−S)≤∣S∣k(G - S) \le |S|k(G−S)≤∣S∣ for every nonempty proper subset SSS of V(G)V(G)V(G) ( kkk = number of components). Must GGG be Hamiltonian?
No. This graph satisfies the condition, but its degree-2 vertices t,x,vt, x, vt,x,v would force three Hamiltonian cycle edges at zzz .
How do the problems "does GGG have an Eulerian circuit?" and "does GGG have a Hamiltonian cycle?" differ in difficulty?
The Eulerian one is easy (all degrees even); for Hamiltonian cycles no useful characterization is known. So one looks for sufficient conditions instead.
Ore's theorem (Theorem 6.6) Let GGG be a graph of order n≥3n \ge 3n≥3 . If deg⁡u+deg⁡v≥ ?\deg u + \deg v \ge \; ?degu+degv≥? for each pair u,vu, vu,v of nonadjacent vertices, then GGG is Hamiltonian.
deg⁡u+deg⁡v≥n\boldsymbol{\deg u + \deg v \ge n}degu+degv≥n
Ore: GGG of order n≥3n \ge 3n≥3 with deg⁡u+deg⁡v≥n\deg u + \deg v \ge ndegu+degv≥n for all nonadjacent u,vu, vu,v is Hamiltonian. Suppose GGG is a counterexample.How does the proof get a Hamiltonian path to work with?
Add edges to GGG while it stays non-Hamiltonian, giving HHH . For nonadjacent x,yx, yx,y of HHH , H+xyH + xyH+xy is Hamiltonian, so HHH has a Hamiltonian xxx – yyy path. H≠KnH \ne K_nH=Kn since KnK_nKn is Hamiltonian. Adding edges keeps the degree-sum condition. Every Hamiltonian cycle of H+xyH + xyH+xy uses xyxyxy .
Ore's proof: HHH is non-Hamiltonian of order nnn with a Hamiltonian path (x=x1,x2,…,xn=y)(x = x_1, x_2, \dots, x_n = y)(x=x1,x2,…,xn=y) , xxx and yyy nonadjacent, and deg⁡Hx+deg⁡Hy≥n\deg_H x + \deg_H y \ge ndegHx+degHy≥n .What is the key observation, and why does it give a contradiction?
If x1xix_1x_ix1xi is an edge, then xi−1xnx_{i-1}x_nxi−1xn is not, so deg⁡xn≤(n−1)−deg⁡x1\deg x_n \le (n - 1) - \deg x_1degxn≤(n−1)−degx1 , i.e. deg⁡x+deg⁡y≤n−1\deg x + \deg y \le n - 1degx+degy≤n−1 . Otherwise (x1,xi,xi+1,…,xn,xi−1,xi−2,…,x1)(x_1, x_i, x_{i+1}, \dots, x_n, x_{i-1}, x_{i-2}, \dots, x_1)(x1,xi,xi+1,…,xn,xi−1,xi−2,…,x1) is a Hamiltonian cycle. Each of the deg⁡x1\deg x_1degx1 neighbors xix_ixi rules out a different xi−1x_{i-1}xi−1 as a neighbor of xnx_nxn .
Ore: if deg⁡u+deg⁡v≥n\deg u + \deg v \ge ndegu+degv≥n for every two nonadjacent vertices of a graph GGG of order n≥3n \ge 3n≥3 , then GGG is Hamiltonian.Which graph shows that nnn can't be lowered to n−1n - 1n−1 ?
Two copies of Kk+1K_{k+1}Kk+1 sharing one vertex, K1+2KkK_1 + 2K_kK1+2Kk , with n=2k+1n = 2k + 1n=2k+1 . The shared vertex is a cut-vertex, so the graph isn't Hamiltonian, yet nonadjacent u,vu, vu,v have deg⁡u+deg⁡v=k+k=n−1\deg u + \deg v = k + k = n - 1degu+degv=k+k=n−1 . Shown: n=7n = 7n=7 .
Dirac's theorem (Corollary 6.7) Let GGG be a graph of order n≥3n \ge 3n≥3 . If deg⁡v≥ ?\deg v \ge \; ?degv≥? for each vertex vvv , then GGG is Hamiltonian.
deg⁡v≥n2\boldsymbol{\deg v \ge \frac{n}{2}}degv≥2n Then nonadjacent u,vu, vu,v have deg⁡u+deg⁡v≥n2+n2=n\deg u + \deg v \ge \frac{n}{2} + \frac{n}{2} = ndegu+degv≥2n+2n=n , and Ore's theorem applies. Gabriel Dirac was the stepson of the physicist Paul Dirac.
Theorem 6.8 (Bondy and Chvátal) Let u,vu, vu,v be nonadjacent vertices of a graph GGG of order nnn with deg⁡u+deg⁡v≥n\deg u + \deg v \ge ndegu+degv≥n . Then … ?
G+uvG + uvG+uv is Hamiltonian if and only if GGG is Hamiltonian.
Bondy–Chvátal: if u,vu, vu,v are nonadjacent in GGG (order nnn ) with deg⁡u+deg⁡v≥n\deg u + \deg v \ge ndegu+degv≥n , and G+uvG + uvG+uv is Hamiltonian, then GGG is Hamiltonian.What is the proof?
If GGG weren't Hamiltonian, every Hamiltonian cycle of G+uvG + uvG+uv would use uvuvuv , so GGG has a Hamiltonian uuu – vvv path; Ore's argument then builds a Hamiltonian cycle. On a Hamiltonian x1x_1x1 – xnx_nxn path of a non-Hamiltonian graph, x1xix_1x_ix1xi and xi−1xnx_{i-1}x_nxi−1xn are never both edges, so deg⁡x1+deg⁡xn≤n−1\deg x_1 + \deg x_n \le n - 1degx1+degxn≤n−1 .
What is the closure C(G)C(G)C(G) of a graph GGG of order nnn ?
The graph obtained by repeatedly joining two nonadjacent vertices whose degree sum is at least nnn (in the current graph), until no such pair remains. Here n=6n = 6n=6 , and C(G)=K6C(G) = K_6C(G)=K6 .
Theorem 6.9. How is a graph's Hamiltonicity related to its closure?
A graph is Hamiltonian if and only if its closure is. Each step joins u,vu, vu,v with deg⁡u+deg⁡v≥n\deg u + \deg v \ge ndegu+degv≥n , which by Bondy–Chvátal doesn't change Hamiltonicity.
Corollary 6.10: a graph of order at least 3 whose closure is complete is Hamiltonian.
The closure is then KnK_nKn , which is Hamiltonian.
Why does Ore's theorem ( deg⁡u+deg⁡v≥n\deg u + \deg v \ge ndegu+degv≥n for all nonadjacent u,vu, vu,v ⇒\Rightarrow⇒ Hamiltonian) follow from the closure?
Every nonadjacent pair already qualifies to be joined, so the closure is KnK_nKn . A graph whose closure is complete is Hamiltonian.
What is the closure of K2,3K_{2,3}K2,3 ?
K2,3K_{2,3}K2,3 plus the edge joining its two vertices of degree 3. n=5n = 5n=5 : the two degree-3 vertices have 3+3≥53 + 3 \ge 53+3≥5 ; afterwards any two degree-2 vertices have only 2+2=42 + 2 = 42+2=4 . (Top: C(C5)=C5C(C_5) = C_5C(C5)=C5 .)
If a graph's closure is not complete, can the graph still be Hamiltonian?
Yes: e.g. C5C_5C5 is its own closure but is Hamiltonian. Nonadjacent vertices of C5C_5C5 have degree sum 4<54 < 54<5 . "Closure complete ⇒\Rightarrow⇒ Hamiltonian" is only sufficient.
Pósa's theorem (Theorem 6.11) Let GGG be a graph of order n≥3n \ge 3n≥3 . If for every integer jjj with 1≤j<n21 \le j < \frac{n}{2}1≤j<2n … ?, then GGG is Hamiltonian.
The number of vertices with degree at most jjj is less than jjj . Lajos Pósa found this as a barely teenage student in Hungary.
Pósa: GGG of order n≥3n \ge 3n≥3 is Hamiltonian if, for every jjj with 1≤j<n21 \le j < \frac{n}{2}1≤j<2n , fewer than jjj vertices have degree at most jjj .What does the condition say for j=1j = 1j=1 and j=2j = 2j=2 ?
j=1j = 1j=1 : no vertex of degree 0 or 1. j=2\ j = 2 j=2 : at most one vertex of degree 2.
Pósa: GGG of order n≥3n \ge 3n≥3 is Hamiltonian if, for every jjj with 1≤j<n21 \le j < \frac{n}{2}1≤j<2n , fewer than jjj vertices have degree at most jjj .The proof shows C(G)C(G)C(G) is complete. How?
Take a nonadjacent pair u,wu, wu,w of C(G)C(G)C(G) with maximum degree sum, deg⁡u=k≤deg⁡w\deg u = k \le \deg wdegu=k≤degw . The non-neighbors of www all have degree ≤k\le k≤k , so there are fewer than kkk of them, which makes deg⁡w\deg wdegw too large. Maximality gives the degree bound on non-neighbors of www . The pair wasn't joined, so deg⁡u+deg⁡w≤n−1\deg u + \deg w \le n - 1degu+degw≤n−1 , i.e. k≤n−12k \le \frac{n-1}{2}k≤2n−1 and deg⁡w≤n−k−1\deg w \le n - k - 1degw≤n−k−1 . Degrees in C(G)C(…
GGG is a connected graph of size mmm ( mmm edges). Why does GGG have a closed spanning walk of length 2m2m2m ?
Doubling every edge gives a multigraph with all degrees even, hence Eulerian; its Eulerian circuit is such a walk in GGG .
What is a Hamiltonian walk in a connected graph GGG , and what is h(G)h(G)h(G) ?
A closed spanning walk of minimum length; h(G)h(G)h(G) is its length. Every connected graph of size mmm has one, with h(G)≤2mh(G) \le 2mh(G)≤2m . Introduced by Goodman and Hedetniemi in 1973.
GGG is connected of order n≥3n \ge 3n≥3 and h(G)h(G)h(G) is the length of a shortest closed spanning walk. When is h(G)=nh(G) = nh(G)=n ?
Exactly when GGG is Hamiltonian. Otherwise h(G)>nh(G) > nh(G)>n .
For a cyclic ordering s:v1,v2,…,vn,vn+1=v1s: v_1, v_2, \dots, v_n, v_{n+1} = v_1s:v1,v2,…,vn,vn+1=v1 of the vertices of a connected graph GGG , what is d(s)d(s)d(s) , and what is the Hamiltonian number h∗(G)h^*(G)h∗(G) ?
d(s)=∑i=1nd(vi,vi+1)\boldsymbol{d(s) = \sum_{i=1}^{n} d(v_i, v_{i+1})}d(s)=∑i=1nd(vi,vi+1) (distances), and h∗(G)=min⁡sd(s)\boldsymbol{h^*(G) = \min_s d(s)}h∗(G)=minsd(s) . Always d(s)≥nd(s) \ge nd(s)≥n , and GGG is Hamiltonian if and only if some d(s)=nd(s) = nd(s)=n .
For this K2,3K_{2,3}K2,3 , compute d(s)d(s)d(s) ( =∑d(vi,vi+1)= \sum d(v_i, v_{i+1})=∑d(vi,vi+1) ) for s:v1,v2,v3,v4,v5,v1s: v_1, v_2, v_3, v_4, v_5, v_1s:v1,v2,v3,v4,v5,v1 and for s:v1,v3,v2,v4,v5,v1s: v_1, v_3, v_2, v_4, v_5, v_1s:v1,v3,v2,v4,v5,v1 . What is h∗(K2,3)h^*(K_{2,3})h∗(K2,3) ?
8 and 6; h∗(K2,3)=6\boldsymbol{h^*(K_{2,3}) = 6}h∗(K2,3)=6 . 2+1+2+2+1=82 + 1 + 2 + 2 + 1 = 82+1+2+2+1=8 and 1+1+1+2+1=61 + 1 + 1 + 2 + 1 = 61+1+1+2+1=6 . Since K2,3K_{2,3}K2,3 (order 5) isn't Hamiltonian, no ordering gives 5.
Theorem 6.12. For every connected graph GGG , how are h∗(G)h^*(G)h∗(G) (minimum of ∑d(vi,vi+1)\sum d(v_i, v_{i+1})∑d(vi,vi+1) over cyclic vertex orderings) and h(G)h(G)h(G) (length of a shortest closed spanning walk) related?
h∗(G)=h(G)\boldsymbol{h^*(G) = h(G)}h∗(G)=h(G)
h(G)h(G)h(G) : length of a shortest closed spanning walk. h∗(G)h^*(G)h∗(G) : minimum of d(s)=∑d(vi,vi+1)d(s) = \sum d(v_i, v_{i+1})d(s)=∑d(vi,vi+1) over cyclic orderings s:v1,…,vn,v1s: v_1, \dots, v_n, v_1s:v1,…,vn,v1 of V(G)V(G)V(G) .Why is h(G)≤h∗(G)h(G) \le h^*(G)h(G)≤h∗(G) ?
Join consecutive vertices of an optimal ordering sss by geodesics (shortest paths): together they form a closed spanning walk of length d(s)d(s)d(s) .
h(G)h(G)h(G) : length of a shortest closed spanning walk. h∗(G)h^*(G)h∗(G) : minimum of d(s)=∑d(vi,vi+1)d(s) = \sum d(v_i, v_{i+1})d(s)=∑d(vi,vi+1) over cyclic orderings s:v1,…,vn,v1s: v_1, \dots, v_n, v_1s:v1,…,vn,v1 of V(G)V(G)V(G) .Why is h∗(G)≤h(G)h^*(G) \le h(G)h∗(G)≤h(G) ?
Order the vertices by their first appearance on a shortest closed spanning walk WWW ; each d(vi,vi+1)d(v_i, v_{i+1})d(vi,vi+1) is at most the length of the viv_ivi – vi+1v_{i+1}vi+1 piece of WWW . The pieces make up WWW , so d(s)≤L(W)=h(G)d(s) \le L(W) = h(G)d(s)≤L(W)=h(G) .
What is the upper Hamiltonian number h+(G)h^+(G)h+(G) of a connected graph GGG ? What is h+(K2,3)h^+(K_{2,3})h+(K2,3) ?
h+(G)=max⁡sd(s)\boldsymbol{h^+(G) = \max_s d(s)}h+(G)=maxsd(s) over cyclic orderings sss of V(G)V(G)V(G) ; h+(K2,3)=8\ h^+(K_{2,3}) = 8 h+(K2,3)=8 . d(s)=∑d(vi,vi+1)d(s) = \sum d(v_i, v_{i+1})d(s)=∑d(vi,vi+1) . For K2,3K_{2,3}K2,3 , every d(s)d(s)d(s) is 6 or 8.
For the Petersen graph PGPGPG , why is 11≤h(PG)≤h+(PG)≤2011 \le h(PG) \le h^+(PG) \le 2011≤h(PG)≤h+(PG)≤20 ?
PGPGPG is non-Hamiltonian of order 10, so h≥11h \ge 11h≥11 ; it has diameter 2, so each of the 10 terms of d(s)d(s)d(s) is at most 2. In fact h(PG)=11h(PG) = 11h(PG)=11 , h+(PG)=20h^+(PG) = 20h+(PG)=20 , and every value from 11 to 20 is d(s)d(s)d(s) for some ordering sss .
Which result and year are considered the beginning of graph theory?
Euler's solution of the Königsberg Bridge Problem, 1736 (the even-degree characterization of Eulerian graphs). Oystein Ore remarked that graph theory is one of the few fields of mathematics with a definite birth date.
Who wrote the first textbook on graph theory, and when?
Dénes König, 1936, “Theorie der endlichen und unendlichen Graphen” (in German). For over 20 years it was the only book on graph theory. König's influence brought Erdős, Gallai and Turán to the field.
Who wrote the second book on graph theory (1958), and what term did he coin?
Claude Berge, “Théorie des graphes et ses applications”; he coined hypergraph. He spread graph theory in France, where many had resisted it.
Whose 1962 book “Theory of Graphs” introduced graph theory to the English-speaking world?
Oystein Ore (Yale).
Which two major graph theory books appeared in 1969?
Alexander Zykov's “Theory of Finite Graphs” and Frank Harary's “Graph Theory”. Harary (University of Michigan) was called the "Ambassador of Graph Theory". William Tutte, writing as Blanche Descartes, wrote the 1969 poem "The Expanding Unicurse" about Königsberg.