Eulerian and Hamiltonian Graphs

In the undirected case, if $s\mathrm{\ne }t$, the used edge ends at $t$ occur in pairs for every intermediate visit and with one additional final arrival. Thus an odd number of edge ends incident with $t$ have been used; loops contribute pairs by [F2]. Since $\mathrm{deg}(t)$ is even, at least one incident edge is unused, contradicting maximality.

In the directed case, if $s\mathrm{\ne }t$, the trail uses one more incoming than outgoing arc at $t$. Total indegree equals total outdegree, so the number of unused outgoing arcs at $t$ is one more than the number of unused incoming arcs and is positive, again contradicting maximality.

Therefore $s=t$ in either case, so the trail is closed.

Rotate the cyclic listing of each closed trail so that it starts and ends at $w$. Traverse $C$ from $w$ back to $w$, then traverse $D$ from $w$ back to $w$. Consecutive edges or arcs still meet at their displayed vertices, and directed arcs retain their orientations.

The concatenation is closed, and it repeats no edge or arc because neither input trail repeats one and their used sets are disjoint. Its used set is exactly the union of the two input used sets.

This concatenation is the required spliced closed trail in either setting.

If $M$ has an Euler circuit, every arrival at a vertex is paired with a departure; a loop supplies both ends of such a pair. Because the circuit uses every edge, every degree is even.

Now suppose every degree is even. If $M$ has no edges, connectedness forces it to have one vertex, and the length-zero closed trail there is an Euler circuit.

If $M$ has an edge, start with that edge and repeatedly extend the trail at its terminal vertex by any unused incident edge until no extension is possible. Finiteness makes this process stop, and [L1] makes the resulting nonempty trail $C$ closed.

After deleting the edges of $C$, every residual degree is even because a closed trail uses an even number of edge ends at each vertex. If an unused edge remains, connectedness of $M$ supplies an underlying path from a vertex of $C$ to that edge; at the first point where this path leaves the used-edge region, an unused edge is incident with a vertex of $C$.

Starting at that vertex, extend a trail using only residual edges until maximal. The residual degrees are even, so [L1] closes it, and [L2] splices it into $C$.

Each splice strictly increases the number of used edges. Since $M$ has finitely many edges, repeating steps 2.1 and 3.1 terminates with one closed trail using every edge, hence an Euler circuit. Together with step 1.1 this proves both directions.

Along any trail, every vertex other than two distinct endpoints uses incident edge ends in pairs. If the trail is open, its two endpoints each use one unpaired end; if it is closed, every used incidence is paired. Loops contribute pairs by [F2].

If every degree is even, [L1] supplies an Euler circuit, which is an Euler trail.

If exactly $u$ and $v$ have odd degree, add one distinguished edge between $u$ and $v$, allowing it to be parallel to an existing edge. The augmented connected multigraph has all degrees even, so [L1] supplies an Euler circuit. Rotate that circuit to begin with the distinguished edge and delete it; what remains is an Euler trail in $M$ from $v$ to $u$.

Therefore an Euler trail forces exactly two odd-degree vertices when open and zero odd-degree vertices when closed.

Steps 2.1, 1.2, and 1.3 prove the criterion and show that openness occurs exactly in the two-odd-vertex case.

A directed Euler circuit uses one incoming and one outgoing arc at each visit, so it gives equal indegree and outdegree at every vertex. Because there are no isolated vertices and every arc lies on the circuit, all vertices lie in one connected underlying graph.

Conversely, suppose $D$ is weakly connected and balanced. The hypotheses and absence of isolated vertices provide an arc. Start with it, repeatedly extend at the terminal vertex by an unused outgoing arc, and stop when none remains. Finiteness gives termination, and [L1] makes the resulting trail $C$ closed.

Deleting the arcs of $C$ leaves equal residual indegree and outdegree at every vertex, because a closed directed trail uses equally many incoming and outgoing arcs there.

If an unused arc remains, take an underlying path from a vertex of $C$ toward an endpoint of an unused arc and stop at the first unused boundary arc incident with $C$. If this arc points out of the incident vertex of $C$, an unused outgoing arc is present there. If it points into that vertex, residual balance from step 2.1 supplies an unused outgoing arc there.

From that vertex, extend using residual outgoing arcs until maximal. By residual balance and [L1] the new trail closes, and [L2] splices it into $C$.

Every splice uses at least one new arc. Finiteness therefore makes repetition of steps 2.1 through 3.1 terminate with one directed closed trail using every arc. This is a directed Euler circuit, and step 1.1 proves the converse necessity.

Deleting the vertices of $S$ from the cyclic order of $C$ leaves one or more vertex-disjoint path segments containing every vertex of $G-S$. Each such segment is preceded around $C$ by a distinct vertex of $S$, so the number of segments is at most $\mathrm{\mid }S\mathrm{\mid }$.

Every path segment from step 1.1 remains a path in $G-S$. Adding the other edges of $G-S$ can merge such segments into a connected component but cannot split one, so $G-S$ has no more components than those segments.

Therefore the number of connected components of $G-S$ is at most $\mathrm{\mid }S\mathrm{\mid }$.

The graph $G$ is connected by [F1]. For any vertex $v$, the set $\{v\}$ is nonempty and proper, and $G-v$ has at least two vertices. By [L1], it has at most one connected component, hence it is connected.

Thus neither the empty set nor a singleton is a vertex cut: deleting nothing preserves connectedness, and deleting one vertex leaves a connected graph with at least two vertices.

Every vertex cut therefore has size at least two, so $\kappa (G)\ge 2$ by [F2].

Every Hamilton cycle of $G$ is also a Hamilton cycle of $G+uv$, so Hamiltonicity of $G$ implies Hamiltonicity of $G+uv$.

Conversely, take a Hamilton cycle of $G+uv$. If it avoids the new edge $uv$, it is already a Hamilton cycle of $G$. If it uses $uv$, deleting that edge leaves a Hamilton path $v_1=u,v_2,\dots ,v_n=v$ in $G$.

For $1\le i\le n-1$, put $i$ in $A$ when $u{v}_{i+1}$ is an edge of $G$, and put $i$ in $B$ when $v_{i}v$ is an edge. Since $u$ and $v$ are nonadjacent, $\mathrm{\mid }A\mathrm{\mid }={\mathrm{deg}}_G(u)$ and $\mathrm{\mid }B\mathrm{\mid }={\mathrm{deg}}_G(v)$. Both lie in an $(n-1)$-element index set, while $\mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }\ge n$, so $A\cap B\mathrm{\ne }\mathrm{\varnothing }$.

Choose $i\in A\cap B$. Then $v_1,v_2,\dots ,v_i,v_n,v_{n-1},\dots ,v_{i+1},v_1$ is a Hamilton cycle in $G$: the two joining edges are $v_{i}v$ and $u{v}_{i+1}$, and all other edges come from the path in step 1.2.

The cases in step 1.2 and the construction in step 2.1 prove that Hamiltonicity of $G+uv$ implies Hamiltonicity of $G$; step 1.1 proves the other direction.

If $G$ has no nonedges, no addition is possible and every maximal sequence terminates at $G$.

Assume the claimed uniqueness holds for every graph with fewer than $k$ nonedges, and let $G$ have $k>0$ nonedges. Once a nonedge is eligible, it remains eligible after other edges are added because degrees do not decrease.

If $G$ has no eligible nonedge, every maximal sequence is empty. Otherwise compare two maximal sequences, whose first added edges are $e$ and $f$. If $e=f$, their tails start at the same graph $G+e$, which has fewer than $k$ nonedges, so the induction hypothesis gives the same terminal graph.

If $e\mathrm{\ne }f$, persistence from step 1.2 makes $f$ eligible after adding $e$ and $e$ eligible after adding $f$. Thus both first-step graphs can legally reach $G+e+f$. Applying the induction hypothesis inside $G+e$ compares its given tail with the tail beginning by $f$; applying it inside $G+f$ compares its given tail with the tail beginning by $e$. Both therefore have the same terminal graph as a maximal continuation from $G+e+f$.

The cases in steps 2.1 and 2.2 establish uniqueness for graphs with $k$ nonedges. By induction, all finite graphs have a unique terminal graph, so the closure is independent of the addition order.

Along any sequence from $G$ to $\mathrm{cl}(G)$, [L1] says after each added edge that the graph before the addition is Hamiltonian exactly when the graph after it is Hamiltonian.

The sequence is finite, and [L2] identifies its terminal graph with the well-defined closure. Chaining the biconditionals from step 1.1 gives $G$ Hamiltonian if and only if $\mathrm{cl}(G)$ is Hamiltonian.

Every nonedge of $G$ is eligible by hypothesis. Eligibility persists as edges are added because degrees cannot decrease, so the closure procedure adds all missing edges and $\mathrm{cl}(G)=K_n$.

Label the vertices of $K_n$ as $v_1,\dots ,v_n$. Since $n\ge 3$, the cycle $v_1,v_2,\dots ,v_n,v_1$ is a Hamilton cycle in $K_n$.

Thus the closure of $G$ is Hamiltonian, and [L1] implies that $G$ is Hamiltonian.

For any nonadjacent vertices $u,v$, [F1] and the hypothesis give $\mathrm{deg}(u)+\mathrm{deg}(v)\ge 2\delta (G)\ge n$.

Since the pair was arbitrary, Ore's degree-sum condition holds for every nonadjacent pair.

By [L1], every nonadjacent pair $u,v$ satisfies $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$.

Since $n\ge 3$, [L2] applies and shows that $G$ is Hamiltonian.

If $n=1$, the one-vertex directed path contains every vertex.

Assume every tournament on $n-1$ vertices has a directed Hamilton path, where $n>1$. Remove a vertex $x$. The remaining tournament has, by the induction hypothesis, a directed Hamilton path $v_1,v_2,\dots ,v_{n-1}$.

If $x{v}_1$ is an arc, prepend $x$. If no arc $x{v}_j$ exists, [F1] gives $v_{j}x$ for every $j$, so append $x$. Otherwise let $j$ be the least index with arc $x{v}_j$; then $j>1$ and minimality plus [F1] gives the arc $v_{j-1}x$. Insert $x$ between $v_{j-1}$ and $v_j$.

In every case the resulting list follows directed arcs and contains each vertex of $T$ exactly once, so it is a directed Hamilton path.

The base case and induction step prove Redei's theorem for every nonempty finite tournament.

Mark a cycle vertex $c_i$ with $I$ when $c_{i}x$ is an arc and with $O$ when $x{c}_i$ is an arc. Both marks occur by hypothesis, and [F1] gives exactly one mark at each cycle vertex. Therefore somewhere around the cyclic order an $I$-marked vertex $c_i$ is followed by an $O$-marked vertex $c_{i+1}$.

Replace the cycle arc $c_i{c}_{i+1}$ by the two arcs $c_{i}x$ and $x{c}_{i+1}$. All other cycle arcs remain unchanged, and $x$ is new, so the resulting closed directed walk is a directed cycle on $V(C)\cup \{x\}$.

This explicitly constructs the required enlarged directed cycle.

Strong connectivity gives a positive directed closed walk. Choose one of minimum positive length. It cannot have length one or two by [F1], and minimality prevents a repeated internal vertex, so it is a directed cycle of length at least three. By finiteness, choose a directed cycle $C$ of greatest length.

Assume for contradiction that $C$ omits at least one vertex. By [L1] and maximality, every vertex outside $C$ either sends arcs to every vertex of $C$ or receives arcs from every vertex of $C$. Call these two classes $A$ and $B$, respectively.

Strong connectivity forces both $A$ and $B$ to be nonempty: if $A$ were empty no outside vertex could reach $C$, while if $B$ were empty $C$ could not reach an outside vertex. A shortest directed path from $C$ to a vertex of $A$ begins by entering $B$ and at some first transition contains an arc $ba$ with $b\in B$ and $a\in A$.

Choose any cycle arc $c_i{c}_{i+1}$. Since $b\in B$ and $a\in A$, the arcs $c_{i}b$, $ba$, and $a{c}_{i+1}$ all occur. Replacing $c_i{c}_{i+1}$ by this three-arc path produces a directed cycle containing every vertex of $C$ together with $a,b$, contradicting the maximality of $C$.

The supposition in step 2.1 is impossible. Hence $C$ contains every vertex of $T$ and is a directed Hamilton cycle.