Eulerian and Hamiltonian Graphs: Examples and Counterexamples

Counting the bridge ends incident with the four land regions gives degrees $5,3,3,3$, so all four vertices have odd degree.

Since four is neither zero nor two, [L1] rules out an Euler trail. Such a trail would be exactly a crossing of every bridge once.

Regard $G$ as the corresponding multigraph from [F2]. It is connected, $\mathrm{deg}(x)=4$, and each of $a,b,c,d$ has degree two. Hence every degree is even, and [L1] gives an Euler circuit; explicitly, $x,a,b,x,c,d,x$ uses every edge once.

Deleting $S=\{x\}$ leaves the two disjoint edges $ab$ and $cd$, hence two connected components. Since $2>\mathrm{\mid }S\mathrm{\mid }=1$, [L2] shows that $G$ cannot have a Hamilton cycle.

Thus $G$ is Eulerian and non-Hamiltonian, refuting the proposed implication.

By completeness, $1,2,3,4,1$ is a cycle through all four vertices, so $K_4$ is Hamiltonian.

Every vertex is adjacent to the other three, so every degree is three. Regard $K_4$ as the corresponding multigraph from [F4]. It is connected, but its degrees are odd; [L1] therefore rules out an Euler circuit.

Hence Hamiltonicity does not imply existence of an Euler circuit.

The path $0,1,2$ uses both edges and contains every vertex exactly once, so it is a Hamilton path.

Deleting the middle vertex $1$ leaves two isolated vertices, hence two components. This violates [L1] for the singleton set $S=\{1\}$, so $P_3$ has no Hamilton cycle.

Therefore a Hamilton path need not extend to a Hamilton cycle.

The graph has $n=2m$ vertices. Every vertex has precisely the other $m-1$ vertices in its own copy as neighbours, so $\delta (G)=m-1=n\mathrm{/}2-1$.

The two copies are distinct connected components because no edge joins them. Hence $G$ is disconnected and cannot be Hamiltonian by [F2].

At the endpoint $m=2$, the construction is two disjoint edges on four vertices, with minimum degree $1=4\mathrm{/}2-1$, so the same failure occurs.

Thus lowering the threshold in [L1] by one for even order would make the theorem false.

Each consecutive pair in the displayed cyclic list has one endpoint in $A$ and one in $B$, so all six required edges occur by [F1].

Before returning to $a_1$, the list contains each of the six vertices exactly once. It is therefore a Hamilton cycle by [F2].

The degree multiset is $\{2,3,3,4,4\}$: $x$ has degree two, $a,b$ have degree four, and $c,d$ have degree three. Thus $\delta (G)=2<5\mathrm{/}2$, so Dirac's hypothesis [L2] fails.

Directly, every consecutive pair in $x,a,c,d,b,x$ is an edge, and the list visits all five vertices once before returning.

The only nonedges are $xc$ and $xd$. Each has endpoint-degree sum $2+3=5$, so Ore's condition holds; [L1] therefore confirms Hamiltonicity.

Hence Ore's condition can hold when Dirac's condition does not, and the displayed Hamilton cycle verifies the conclusion.

For each distinct pair $i,j$, exactly one of $i<j$ and $j<i$ holds, so the construction is a tournament by [F1]. Each arc in the list $1,2,\dots ,n$ points forward, and the list contains every vertex once, so it is a directed Hamilton path, explicitly realizing [L1].

Along every directed walk in this tournament, the vertex label strictly increases at each positive-length step. Such a walk cannot return to its initial label, so no directed cycle exists.

Thus a tournament may have a directed Hamilton path while having no directed cycle.

The three arcs orient the three unordered vertex pairs exactly once, so $T$ is a tournament. The ordered pairs $(1,2),(2,3),(3,1)$ are joined directly, while $(2,1),(3,2),(1,3)$ are joined by the two-arc paths through the remaining vertex. Hence $T$ is strongly connected.

The closed list $1,2,3,1$ follows the three arcs and visits every vertex once before returning, so it is a directed Hamilton cycle, as [L1] predicts.

This verifies all three assertions in the example.