140 Euler Hamilton
140.1 Euler Hamilton
G is eulerian: it has a closed Euler trail (an Euler tour).
A trail that traverses every edge of \(G\) is called an Euler trail of \(G\) because Euler was the first to investigate the existence of such trails in graphs.
A tour of \(G\) is a closed walk that traverses each edge of \(G\) at least once. An Euler tour is a tour which traverses each edge exactly once (in other words, a closed Euler trail). A graph is eulerian if it contains an Euler tour.
Component count \(\omega \)(G).
\(\omega \)(G) is the number of components of G — the classes into which the equivalence relation "is connected to" partitions the vertex set. Defined in chapter 1, not chapter 4, so there is no chapter-4 text to quote.
Join G \(\lor \) H, rebuilt on Mathlib: within-side edges from \(\oplus \)g, all cross edges from completeBipartiteGraph. symm/loopless are inherited from \(\sqcup \).
We first introduce the notion of the join of two graphs. The join \(G \vee H\) of disjoint graphs \(G\) and \(H\) is the graph obtained from \(G + H\) by joining each vertex of \(G\) to each vertex of \(H\); it is represented diagrammatically as in figure 4.8.
C_{m,n} = K_m \(\lor \) (K_m^c + K_{n-2m}), with + the Mathlib disjoint sum \(\oplus \)g.
Now, for \(1 \le m \lt n/2\), let \(C_{m,n}\) denote the graph \(K_m \vee (K_m^c + K_{n-2m})\), depicted in figure 4.9a; two specific examples, \(C_{1,5}\) and \(C_{2,5}\), are shown in figures 4.9b and 4.9c.
That \(C_{m,n}\) is nonhamiltonian follows immediately from theorem 4.2; for if \(S\) denotes the set of \(m\) vertices of degree \(n-1\) in \(C_{m,n}\), we have \(\omega (C_{m,n} - S) = m + 1 \gt |S|\).
Theorem 4.6 then shows these are the extreme nonhamiltonian graphs: every nonhamiltonian simple graph is degree-majorised by some C_{m,\(\nu \)}. C_{1,\(\nu \)} and C_{2,5} reappear as the extremal cases of Corollary 4.6.
The sorted (ascending) degree sequence of G.
Listing the vertices as v\(_{1}\), …, v_\(\nu \), the sequence (d(v\(_{1}\)), …, d(v_\(\nu \))) is a degree sequence of G. Chapter 4 always takes it in nondecreasing order — as in the hypothesis of Theorem 4.5 (§4.2, p. 65):
Let \(G\) be a simple graph with degree sequence \((d_1, d_2, \ldots , d_\nu )\), where \(d_1 \leq d_2 \leq \ldots \leq d_\nu \) and \(\nu \geq 3\).
which is why this definition sorts ascending.
G is degree-majorised by H: same order, and every sorted-degree entry of G is \(\le \) the corresponding entry of H.
A sequence of real numbers \((p_1, p_2, \ldots , p_n)\) is said to be majorised by another such sequence \((q_1, q_2, \ldots , q_n)\) if \(p_i \le q_i\) for \(1 \le i \le n\). A graph \(G\) is degree-majorised by a graph \(H\) if \(\nu (G) = \nu (H)\) and the nondecreasing degree sequence of \(G\) is majorised by that of \(H\). For instance, the 5-cycle is degree-majorised by \(K_{2,3}\) because \((2, 2, 2, 2, 2)\) is majorised by \((2, 2, 2, 3, 3)\).
One Bondy–Chvátal closure step: add a nonadjacent pair whose degree sum is \(\ge \) \(\nu \).
Lemma 4.4.1 motivates the following definition. The closure of \(G\) is the graph obtained from \(G\) by recursively joining pairs of nonadjacent vertices whose degree sum is at least \(\nu \) until no such pair remains. We denote the closure of \(G\) by \(c(G)\).
\(c(G)\) is well defined.
Its proof (the "first edge not in G\(_{2}\)" argument) is quoted on hamiltonian_iff_of_closureSteps below, which is where the content is used.
G is Hamilton-connected: every ordered pair is joined by a Hamilton path (Ex 4.2.11).
4.2.11 \(G\) is Hamilton-connected if every two vertices of \(G\) are connected by a Hamilton path. (a) Show that if \(G\) is Hamilton-connected and \(\nu \ge 4\), then \(\varepsilon \ge [\frac{1}{2}(3\nu +1)]\). (b)* For \(\nu \ge 4\), construct a Hamilton-connected graph \(G\) with \(\varepsilon = [\frac{1}{2}(3\nu +1)]\). (J. W. Moon)
G is hypohamiltonian: not Hamiltonian, but every vertex-deleted subgraph is (Ex 4.2.12).
4.2.12 \(G\) is hypohamiltonian if \(G\) is not hamiltonian but \(G - v\) is hamiltonian for every \(v \in V\). Show that the Petersen graph (figure 4.4) is hypohamiltonian. (Herz, Duby and Vigué, 1967 have shown that it is, in fact, the smallest such graph.)
Let \(G\) be a finite simple graph that is connected and has at least one edge. Then \(G\) is eulerian — that is, it admits an Euler tour, a closed walk traversing each edge exactly once — if and only if every vertex of \(G\) has even degree.
Let \(G\) be a connected simple graph on a finite vertex set \(V\). Then \(G\) admits an Eulerian trail — a walk between some pair of vertices \(u,v\) that traverses every edge of \(G\) exactly once — if and only if the number of vertices of odd degree is at most \(2\).
Let \(G\) be a finite simple graph with vertex set \(V\), and suppose \(G\) has a Hamiltonian cycle. Then for every nonempty proper subset \(S \subsetneq V\), the number of connected components of the induced subgraph \(G - S\) obtained by deleting the vertices of \(S\) satisfies
Let \(G\) be a finite simple graph on \(n\) vertices, where \(n \ge 3\), and suppose every vertex has degree at least \(n/2\) (equivalently, \(n \le 2\delta \), where \(\delta \) denotes the minimum degree of \(G\)). Then \(G\) is Hamiltonian, that is, \(G\) contains a cycle passing through every vertex exactly once.
Let \(G\) be a finite simple graph on a vertex set with \(n\) vertices, and let \(u\) and \(v\) be two distinct, nonadjacent vertices of \(G\) whose degrees satisfy \(\deg (u) + \deg (v) \ge n\). Then \(G\) is Hamiltonian if and only if the graph \(G + uv\), obtained from \(G\) by adding the edge joining \(u\) and \(v\), is Hamiltonian.
Let \(G\) be a finite simple graph on \(\nu \) vertices, and suppose \(H\) is obtained from \(G\) by a finite sequence (possibly empty) of Bondy–Chvátal closure steps, each of which selects two distinct nonadjacent vertices whose degrees sum to at least \(\nu \) and joins them by an edge. Then \(G\) is Hamiltonian if and only if \(H\) is Hamiltonian.
Let \(G\) be a finite simple graph on \(\nu \ge 3\) vertices. Suppose the complete graph on the vertices of \(G\) can be obtained from \(G\) by finitely many (possibly zero) Bondy–Chvátal closure steps, each of which joins some pair of distinct nonadjacent vertices whose degrees sum to at least \(\nu \). Then \(G\) is Hamiltonian, that is, \(G\) has a cycle through all of its vertices.
Let \(V\) be a finite vertex set with \(\left\lvert V\right\rvert \ge 3\). Then the complete graph on \(V\) — the simple graph in which every pair of distinct vertices is joined by an edge — is Hamiltonian; that is, it contains a cycle passing through every vertex of \(V\) exactly once.
Let \(G\) be a finite simple graph on \(n \ge 3\) vertices, and write \(\deg (v)\) for the degree of a vertex \(v\). Suppose that for every integer \(m\) with \(1 \le m\) and \(2m \lt n\), it is not the case that both \(G\) has at least \(m\) vertices of degree at most \(m\) and \(G\) has at least \(n - m\) vertices of degree strictly less than \(n - m\). Then \(G\) is Hamiltonian, that is, \(G\) possesses a Hamiltonian cycle.
Let \(G\) be a finite simple graph on \(n \ge 3\) vertices, and suppose \(G\) is not Hamiltonian. Then there is an integer \(m\) with \(0 \lt m\) and \(2m \lt n\) such that \(G\) is degree-majorised by \(C_{m,n}\) (Chvátal, 1972).
Let \(G\) be a finite simple graph on \(n\) vertices with \(n \ge 3\). If the number of edges of \(G\) exceeds \(\binom {n-1}{2} + 1\), then \(G\) is Hamiltonian, that is, \(G\) contains a spanning cycle.
Let \(G\) be a finite simple graph on \(\nu \ge 3\) vertices that is not Hamiltonian and has exactly \(\binom {\nu -1}{2}+1\) edges. Then \(G\) is isomorphic to \(C_{1,\nu }\), unless \(\nu = 5\), in which case \(G\) is isomorphic to either \(C_{1,5}\) or \(C_{2,5}\).
Let \(G\) be a finite simple graph in which every vertex has even degree. Then the edges of \(G\) can be decomposed into cycles: there is a finite collection of cycles \(C_1, C_2, \ldots , C_m\) in \(G\) such that every edge of \(G\) lies in exactly one of the \(C_i\).
Let \(G\) be a connected simple graph on a finite vertex set, and let \(k \ge 1\). Suppose that \(G\) has exactly \(2k\) vertices of odd degree. Then there exist \(k\) trails \(Q_1, \dots , Q_k\) in \(G\) such that every edge of \(G\) lies in exactly one of them; that is, the trails are pairwise edge-disjoint and their edge sets together exhaust \(E(G)\).
Let \(G\) be a finite simple graph on at least three vertices, and suppose its vertex connectivity satisfies \(\kappa (G) \lt 2\) (equivalently, \(G\) is not \(2\)-connected). Then \(G\) is nonhamiltonian; that is, \(G\) has no Hamiltonian cycle.
Let \(G\) be a finite simple graph, and let \(X\) and \(Y\) be disjoint sets of its vertices such that every edge of \(G\) joins a vertex of \(X\) to a vertex of \(Y\). If \(\left\lvert X\right\rvert \neq \left\lvert Y\right\rvert \), then \(G\) is not Hamiltonian; that is, \(G\) has no cycle passing through every vertex of \(G\).
Let \(G\) be a finite simple graph on vertex set \(V\), and suppose \(G\) has a Hamilton path, that is, a path passing through every vertex of \(G\) exactly once. Then for every nonempty proper subset \(S \subsetneq V\), the graph \(G - S\) obtained by deleting the vertices of \(S\) has at most \(\left\lvert S\right\rvert + 1\) connected components.
Let \(G\) be a simple graph on \(\nu \ge 2\) vertices, with degrees arranged in nondecreasing order as \(d_1 \le d_2 \le \cdots \le d_\nu \). Suppose there is no integer \(m\) with \(1 \le m \lt (\nu +1)/2\) for which both \(d_m \lt m\) and \(d_{\nu -m+1} \lt \nu - m\). Then \(G\) has a Hamilton path, that is, a path that passes through every vertex of \(G\) exactly once. (Chvátal)
Let \(G\) be a finite simple graph, and suppose \(G\) is self-complementary, meaning there is a graph isomorphism between \(G\) and its complement \(G^c\). Then \(G\) has a Hamilton path: there exist vertices \(a\) and \(b\) and a walk from \(a\) to \(b\) in \(G\) that visits every vertex of \(G\) exactly once.
Let \(G\) be a finite simple graph on \(n\) vertices with complement \(G^{c}\), and arrange the vertex degrees of each graph in nondecreasing order, writing \(d_{0} \le d_{1} \le \cdots \le d_{n-1}\) for the sorted degree sequence of \(G\) and \(d'_{0} \le d'_{1} \le \cdots \le d'_{n-1}\) for that of \(G^{c}\). If \(d'_{m} \le d_{m}\) for every index \(m\) with \(2m \le n\), then \(G\) has a Hamiltonian path: there are vertices \(a\) and \(b\) and a walk from \(a\) to \(b\) that visits every vertex of \(G\) exactly once.
Let \(G\) be a finite simple graph with \(n\) vertices and \(m\) edges, and let \(\delta \) denote its minimum degree. If \(6\delta \le n\) and
then \(G\) is Hamiltonian, that is, \(G\) contains a cycle passing through every vertex exactly once. (P. Erdős)
Let \(G\) be a connected simple graph on a finite vertex set, with minimum degree \(\delta (G)\) and order \(n\). If \(2\, \delta (G) \lt n\), then \(G\) contains a path of length at least \(2\, \delta (G)\); that is, there exist vertices \(a\) and \(b\) and a path from \(a\) to \(b\) in \(G\) with at least \(2\, \delta (G)\) edges.
Let \(k \ge 1\) be an integer, and let \(G\) be a finite simple graph on \(4k+1\) vertices in which every vertex has degree exactly \(2k\). Then \(G\) has a Hamiltonian cycle, that is, a cycle passing through every vertex of \(G\) exactly once.
Let \(G\) be a finite simple graph on \(\nu \ge 4\) vertices with \(\varepsilon \) edges. If \(G\) is Hamilton-connected — that is, every two distinct vertices of \(G\) are joined by a Hamilton path — then