Eulerian and Hamiltonian Graphs

If the degree of each vertex in a graph is at least two, show that there is a cycle in the graph.

Show that a connected graph is Eulerian if and only if the degree of each vertex of the graph is even.

(The Königsberg Bridge Problem) The two islands (say the East Island and the West Island) in the river Pregel (known as Pregolya these days) that flows from east to west through the city of Königsberg (now known as Kaliningrad) in eastern Prussia (now a part of Russia) were connected by a bridge. Two bridges connected the west island $(W)$ to the north shore $(N)$, and two bridges connected it to the south shore $(S)$. A bridge connected the east island $(E)$ and the north shore, and another bridge connected it to the south shore. Show that the following problem posed to Leonard Euler (in 1736) by the citizens of Königsberg is not solvable: Start from one of these four land masses in the city and return to that point after walking along each bridge exactly once.

Solve the modified Königsberg bridge problem by:

Show that a graph is Eulerian if and only if it is connected and if the set of its edges can be partitioned into a disjoint union of cycles.

Show that a connected graph is Eulerian if and only if every edge in it belongs to an odd number of cycles.

Show that any trail constructed by Fleury's algorithm in an Eulerian graph is an Eulerian circuit.

Using Fleury's algorithm, obtain an Eulerian circuit in the graph of Fig. 3-18.

Fig. 3-18

If the number of odd vertices in a connected graph $G=(V, E)$ is $2 k$, show that the set $E$ can be partitioned into $k$ subsets such that the edges in each subset constitute a trail between two odd vertices.

Locate the odd vertices in the graph of Fig. 3-19 and then partition the set of edges in the graph into subsets such that the edges in each subset constitute a trail.

Fig. 3-19

Prove Theorem 3.2: A connected graph is semi-Eulerian if and only if the number of odd vertices in it is exactly two. Furthermore, in a semi-Eulerian graph, any Eulerian trail is between its two odd vertices.

Prove that a weakly connected digraph is Eulerian if and only if the indegree of each vertex is equal to its outdegree.

A weakly connected digraph is semi-Eulerian if and only if there are two vertices $v$ and $w$ in it such that (1) (outdegree of $v)=($ indegree of $v)+1$, (2) (outdegree of $w)=($ indegree of $w)-1$, and (3) the outdegree of every other vertex is equal to its indegree. Show that in a weakly connected digraph satisfying these three properties, any directed Eulerian trail is from $v$ to $w$.

If every vertex in a graph $G$ is even, no edge in that graph is a bridge.

Find all positive integers $n$ such that $K_{n}$ is:

If $L(G)$ is the line graph of a simple graph $G$, show that $L(G)$ is Eulerian whenever $G$ is Eulerian.

Show that if the line graph of a simple graph $G$ is Eulerian, it is not necessary that $G$ is Eulerian.

Show that a digraph that has an Eulerian circuit is a strongly connected digraph. Is the converse true?

Show that a digraph that has an Eulerian trail is a unilaterally connected digraph. Is the converse true?

Show that if the degree of every vertex of a connected multigraph $G=(V, E)$ is 4, the graph has two spanning subgraphs such that (1) the degree of each vertex in these two subgraphs is 2, (2) the two subgraphs have no edge in common, and (3) $E$ is the union of the sets of edges of these two subgraphs.

Obtain a 2-factor decomposition of the 4-regular graph shown in Fig. 3-20.

Fig. 3-20

Obtain a 2-factor decomposition of the complete bipartite graph $K_{4.4}$.

A graph is said to be an even graph if the degree of every vertex in the graph is even. Find the number of nonequivalent labeled even graphs with $(n+1)$ vertices with labels $1,2, \ldots ,(n+1)$.

A graph $G$ is randomly Eulerian from a vertex $\boldsymbol {v}$ if every trail in the graph starting from $v$ can be extended to a circuit terminating at $v$ that consists of all the edges of the graph. Show that the graph in Fig. 3-22 is randomly Eulerian only from vertex 1.

Fig. 3-22

Prove that

Show that if $G$ is randomly Eulerian from $v, G-v$ is acyclic. Also show that if $v$ is a vertex in an Eulerian graph $G$ such that $G-v$ is acyclic, $G$ is randomly Eulerian from $v$.

If graph $G$ is randomly Eulerian from a vertex, show that the degree of that vertex is equal to $\Delta (G)$, which is the maximum among the degrees of all its vertices. Show that an arbitrary Eulerian graph need not be randomly Eulerian from a vertex of maximum degree.

Show that if $G$ is randomly Eulerian from $v$ and if $w$ is another vertex such that both $v$ and $w$ have the same degree, $G$ is randomly Eulerian from $w$ as well.

A graph is randomly Eulerian if it is randomly Eulerian from every vertex in the graph. Obtain a necessary and sufficient condition for a graph to be randomly Eulerian.

Show that if a graph is not randomly Eulerian, it is randomly Eulerian from at most two of its vertices.

A digraph is a randomly Eulerian digraph from a vertex $\boldsymbol {v}$ if every directed trail of the digraph starting from $v$ can be extended to an Eulerian circuit. Prove that:

If $W$ is the set $\left\{ 0,1,2, \ldots , p-1\right\}$, any linear arrangement (repetitions are allowed) using some of or all these numbers is called a word in the alphabet $W$. Any word with $n$ numbers from $W$ is called an $n$-letter word in $W$. The set of all $n$-letter words in the alphabet $W$ with $p$ numbers is denoted by $W(p, n)$. The de Bruijn digraph $\boldsymbol {G}(\boldsymbol {p}, \boldsymbol {n})$ is constructed by the following inductive procedure. Suppose all the words in $W(p, k)$ are known for $k=1,2, \ldots ,(n-1)$. The vertex set of $G(p, n)$ is $W(p, n-1)$. If $t$ is any $(n-2)$-letter word, and if $i$ and $j$ are numbers (not necessarily distinct) in $W$, draw arcs (for each $i$ ) from vertex it to vertex $t j$ as $j$ varies from 0 to $p-1$. Then the arc from $x t$ to $t y$ represents the $n$-letter word $x t y$. Find the order and size of the de Bruijn digraph $G(p, n)$, and show that it is an Eulerian digraph.

Construct the de Bruijn digraph $G(3,2)$.

If $x=21134$ is a word in $W(4,5)$, construct the arcs:

If $p$ and $n$ are two positive integers and if $p^{n}=r$, a sequence $\langle a(0), a(1), \ldots , a(r-1)\rangle$, where each $a(i)$ is in $W=\left\{ 0,1,2, \ldots , p-1\right\}$, is called a de Bruijn sequence, denoted by $B(p, n)$, if and only if any $n$-letter in $W$ is of the form $a(i) a(i+1) \cdots a(i+n-1)$, where $i$ is at most $r$ and where addition of the subscripts is modulo $r$. (Equivalently, these $r$ numbers in the sequence form a circular arrangement such that any choice of $n$ consecutive (in the clockwise direction) numbers in this arrangement gives a unique word.) Show that a de Bruijn sequence exists for every choice of $p$ and $n$.

Obtain a de Bruijn sequence such that any three-letter word using 0,1, and 2 can be obtained from this sequence.

A rotating drum has $2^{p}$ sectors. The problem is to assign each sector the label 0 or 1 such that no two sequences of $p$ consecutive labels are the same. Solve this problem when:

Show that there are two unique four-letter binary words that can be deleted from the set of all such words so that any of the remaining words can be obtained by selecting four consecutive elements in a binary sequence placed in a circular arrangement. Obtain such a binary sequence.

(Bondy and Chvátal) Let $u$ and $v$ be two nonadjacent vertices in a simple graph $G=(V, E)$ of order $n$ such that the sum of their degrees is at least $n$, and let $G+u v$ be the graph obtained from $G$ by joining these two nonadjacent vertices. Then $G$ is Hamiltonian if and only if $G+u v$ is Hamiltonian.

The closure $\boldsymbol {c}(\boldsymbol {G})$ of a graph $G$ of order $n$ is obtained from $G$ by recursively joining pairs of nonadjacent vertices whose degree sum is at least $n$ until no such pair exists. Show that every graph has a unique closure.

Show that a graph is Hamiltonian if and only if its closure is Hamiltonian.

Show that to establish a graph is Hamiltonian, it is sufficient if we show that its closure is complete.

Give an example of a Hamiltonian graph whose closure is not complete.

(Chvátal's Theorem) If the $n$ vertices $(n \geq 3)$ of a graph $G=(V, \mathrm{E})$ are labeled such that their degrees $d_{i}(i=1,2, \ldots , n)$ can be arranged as a sequence $d_{1} \leq d_{2} \leq \ldots \leq d_{n}$, and if $d_{n-k} \geq (n-k)$ whenever $d_{k} \leq k<n / 2, G$ is Hamiltonian.

If the $n$ vertices $(n \geq 3)$ of a graph $G=(V, \mathrm{E})$ are labeled such that their degrees $d_{i}(i=1,2, \ldots , n)$ can be arranged as a sequence $d_{1} \leq d_{2} \leq \ldots \leq d_{n}$, and if $d_{j}+d_{k} \geq n$ whenever $d_{j} \leq j<k$ and $d_{k} \leq (k-1), G$ is Hamiltonian.

If the $n$ vertices $(n \geq 3)$ of a graph $G=(V, \mathrm{E})$ are labeled such that their degrees $d_{i}(i=1,2, \ldots , n)$ can be arranged as a sequence $S: d_{1} \leq d_{2} \leq \ldots \leq d_{n}$, and if $d_{k}>k$ whenever $1 \leq k<n / 2, G$ is Hamiltonian.

Prove Ore's theorem (Theorem 3.5) using Posa's theorem.

Point out the implications regarding sufficient conditions (established in this sequel) for the existence of a spanning cycle in a graph.

Show that Chvátal's condition is not a necessary condition for the existence of a spanning cycle in a graph.

Show that Chvátal's theorem is stronger than Bondy's theorem.

Show that Bondy's theorem is stronger than Posa's theorem.

Show that Posa's theorem is stronger than Ore's theorem.

Show that Ore's theorem is stronger than Dirac's theorem.

If $G=(V, W, E)$ is a bipartite graph with $\left|V\right|=\left|W\right|=n$, and if the degree of each vertex is more than $n / 2, G$ is Hamiltonian.

Show that if $G$ is Eulerian, its line graph $L(G)$ is Hamiltonian. Give a counterexample to show that the converse is not true.

Show that if a graph $G$ is Hamiltonian, its line graph $L(G)$ is Hamiltonian. Give a counterexample to show that the converse is not true.

Prove Theorem 3.7: A graph $G$ with $n$ vertices ( $n$ is at least three) is Hamiltonian-connected if the sum of the degrees of any two nonadjacent vertices is more than $n$. In particular, it is Hamiltonian-connected if the degree of each vertex is more than $n / 2$.

Give a counterexample to show that the sufficient conditions established in Problem 3.60 for a graph to be Hamiltonian-connected are not necessary conditions.

Define the concept of closure in the context of graphs that are Hamiltonian-connected. Show that the closure of $G$ thus defined is unique. State and prove the appropriate theorem in this context.

Give an example of a Hamiltonian-connected graph whose closure as defined in Problem 3.62 is not complete.

Show that if a graph with $n$ vertices $(n>3)$ and $m$ edges is Hamilton-connected, it is necessary that $m \geq (3 n) / 2$. Show that this condition is by no means sufficient for a graph to be Hamiltonian-connected.

A Hamiltonian graph is said to be strongly Hamiltonian if every edge in the graph belongs to a Hamiltonian cycle. Give an example of:

Show that a Hamiltonian-connected graph is a strongly Hamiltonian graph. Is the converse true?

Obtain a sufficient condition for a graph to be strongly Hamiltonian.

Show that if the degree sum of every pair of nonadjacent vertices in a non-Hamiltonian-connected graph with three or more vertices is at least $k$ (where $k$ is some positive integer), the graph contains a path of length $k$.

If the degree sum of every pair of nonadjacent vertices in a graph of order $n$ is at least $(n-1)$, the graph has a Hamiltonian path. In particular, if the degree of each vertex is at least $(n-1) / 2$, the graph has a Hamiltonian path.

A graph $G$ is randomly traceable if a Hamiltonian path results upon starting from any vertex and successively proceeding to any adjacent vertex that is not yet in the path. Furthermore, if $G$ has at least three vertices and the terminal vertex of each such path is adjacent to the initial vertex, the graph is called randomly Hamiltonian. Obviously, cyclic graphs and complete graphs with three or more vertices are randomly traceable and randomly Hamiltonian. Show that:

Show that if $C=\left\langle v_{1}, v_{2}, \ldots , v_{n}, v_{1}\right\rangle$ is a Hamiltonian cycle in a randomly Hamiltonian graph and if there is an edge in the graph between $v_{j}$ and $v_{k}$, there is an edge between $v_{j+i}$ and $v_{k+i}$ for $i= 1,2, \ldots , n-1$. (Here the addition of the subscripts is modulo $n$.)

Show that if $C=\left\langle v_{1}, v_{2}, \ldots , v_{n}, v_{1}\right\rangle$ is a Hamiltonian cycle in a randomly Hamiltonian graph $G$ and if there is an edge between $v_{p}$ and $v_{p+2}$ (for some $p$ ), $G$ is a complete graph.

Let $G$ be a randomly Hamiltonian graph of order $n$, and let $C$ be any fixed Hamiltonian cycle in this graph. The edges in $C$ are called cycle edges, and the edges not in $C$ are called diagonal edges. Any cycle $C^{\prime }$ consisting of $(k-1)$ cycle edges and exactly one diagonal edge is called an outer $\boldsymbol {k}$-cycle. Show that the minimum value of $k$ such that $G$ has an outer $k$-cycle is either 3 or 4. Furthermore, if $k=3$, the graph is a complete graph, and if $k=4$, the number of vertices in the graph is even.

Show that a graph with three or more vertices is randomly Hamiltonian if and only if it is a cyclic graph or a complete graph or a complete bipartite graph with equal number of vertices in each part.

Show that the cyclic graph is the only graph that is both randomly Eulerian and randomly Hamiltonian.

A graph $G$ is strongly randomly traceable if for every two distinct vertices $u$ and $v$, a Hamiltonian path between $u$ and $v$ exists whenever we start from $u$ and successively proceed to another vertex not yet encountered, with the restriction that $v$ will be chosen only when there is no other alternative. Show that a graph $G$ of order $n$ is a strongly randomly traceable graph if and only if it is the complete graph $K_{n}$.

The outdegree of a vertex in a tournament can be considered as the score of the player represented by that vertex. A player with maximum score is a winner. If $u$ is a player who has defeated a winner $w$ in the tournament, show that $w$ has defeated some player who has defeated $u$.

A graph (digraph) of order $n(n \geq 3)$ is vertex-pancyclic if every vertex is contained in a cycle (directed cycle) of length $p$ for every $p(3 \leq p \leq n)$. Show that a strongly connected tournament is vertex-pancyclic.

Prove Theorem 3.13: A tournament is Hamiltonian if and only if it is strongly connected.

Obtain a necessary and sufficient condition to be satisfied by a vertex in a tournament so that there is a Hamiltonian path starting from that vertex.

A tournament $G=(V, E)$ is irreducible whenever $W$ is a subset of $V$, there should be an arc from a vertex in $W$ to a vertex in $V-W$. Show that in a tournament $G=(V, E)$, the following concepts are equivalent:

Show that every tournament is either a strongly connected digraph or a digraph that can be converted into a strongly connected digraph by reversing the orientation of exactly one arc.

The sequence $\left\langle s_{1}, s_{2}, \ldots , s_{n}\right\rangle$ of nonnegative integers is called a score sequence (of a tournament) if there exists a tournament of order $n$ whose vertices can be labeled $v_{i}$ so that the outdegree of each $v_{i}$ is $s_{i}$ for each $i=1,2, \ldots , n$. Show that a nondecreasing sequence of $n$ nonnegative integers is the score sequence of a transitive tournament if and only if the sequence is $\langle 0,1,2, \ldots , n-1\rangle$.

Show that the sequence $\left\langle s_{1}, s_{2}, \ldots , s_{n}\right\rangle$ of nondecreasing nonnegative integers is a score sequence of a tournament if and only if $s_{1}+s_{2}+\cdots +s_{k} \geq k(k-1) / 2$ for $1 \leq k \leq n$ with equality holding when $k=n$.

Show that the sequence $\left\langle s_{1}, s_{2}, \ldots , s_{n}\right\rangle$ of nondecreasing nonnegative integers is a score of a strongly connected tournament if and only if $s_{1}+s_{2}+\cdots +s_{k}>k(k-1) / 2$ for $1 \leq k \leq (n-1)$ and $s_{1}+ s_{2}+\cdots +s_{n}=n(n-1) / 2$.

If $G$ is a connected graph with $k$ odd vertices, find the minimum number of trails in $G$ such that every edge in the graph is an edge in exactly one of these trails.

Show that if a multidigraph has an Eulerian walk but not an Eulerian circuit, exactly one vertex has an excess of one indegree and exactly one vertex has an excess of one outdegree.

Show that if a graph has a circuit of odd length, it has a cycle of odd length.

Suppose in a group of $n$ people $(n>3)$, any two of them together know all the other people in the group. Show that these $n$ people can be seated around a circular table so that each person is seated between two acquaintances.

Show that a $k$-regular graph with $(2 k-1)$ vertices is Hamiltonian.

Show that any $k$-regular simple graph with $(2 k-1)$ vertices is Hamiltonian.

A nontrivial connected graph is Eulerian if and only if every block in the graph is Eulerian.

Find the number of Hamiltonian graphs in $K_{n}$.

Find the number of Hamiltonian cycles in $K_{n, n}$.

Show that if $n$ is odd, the set of edges of $K_{n}$ can be partitioned into $\frac{1}{2}(n-1)$ disjoint Hamiltonian cycles.

Thirteen mathematicians are attending a six-day conference. Each night they sit around a circular table for dinner so that no two persons sit next to each other more than once and so that each person gets a chance to sit to next to each other person exactly once during those six nights.

Show that the sum of the squares of the terms in the score sequence of a tournament is equal to the sum of the squares of the indegrees of the vertices.

Show that a regular tournament is strongly connected.

Show that if $\left\langle s_{1}, s_{2}, \ldots , s_{n}\right\rangle$ is the score sequence of a tournament, $\left\langle t_{1}, t_{2}, \ldots , t_{n}\right\rangle$ is also a score sequence of a tournament, where $t_{i}=(n-1)-s_{i}$ for $i=1,2, \ldots , n$.

Examine the case when the inequalities in the statement of Problem 3.85 are all equalities.

Show that in a tournament involving $n$ players, the number of players with the score $(n-1)$ is at most 1.

Show that if $n$ is an odd number other than 1, there is a tournament of order $n$ in which every vertex is a winner.

Show that the $k$-cube (see Solved Problem 1.56) is a Hamiltonian graph.

For what value of $k$ is the $k$-cube graph an Eulerian graph?

Show that the de Bruijn digraph is a Hamiltonian graph.