Eulerian and Hamiltonian Graphs

In the complete graph $K_5$ on $\{1,2,3,4,5\}$ (all $\binom52 = 10$ edges), every vertex has degree $4$, which is even, and the graph is connected, so Euler's theorem guarantees a circuit. One alternates between the outer $5$-cycle and the pentagram of long diagonals:

Check: the ten edges used, in order, are $12, 23, 34, 45, 51, 13, 35, 52, 24, 41$ — exactly the ten unordered pairs from $\{1,\ldots,5\}$, each appearing once, and the walk returns to where it started.

Delete edge $cd$ from $K_4$ on $\{a,b,c,d\}$, leaving $ab, ac, ad, bc, bd$. The degree sequence is $\deg(a) = \deg(b) = 3$ and $\deg(c) = \deg(d) = 2$: exactly two odd vertices, so Euler's theorem promises a trail from $a$ to $b$, not a circuit. One is

which uses $ac, cb, bd, da, ab$ — all five edges once, starting and ending at the two odd vertices.

Now restore edge $cd$, so every vertex of $K_4$ has degree $3$. Four vertices of odd degree is already too many: Euler's theorem allows at most two. So $K_4$ has neither an Euler circuit nor an Euler trail, no matter how the six edges are ordered — some vertex other than a start or an end would need an odd number of trail-edges at it, which no trail can give it.

Count the bridges at each landmass: $\deg(A) = 2 + 1 = 3$ (two to $C$, one to $D$), $\deg(B) = 2 + 1 = 3$, $\deg(C) = 2 + 2 + 1 = 5$ (two to $A$, two to $B$, one to $D$), $\deg(D) = 1 + 1 + 1 = 3$. All four degrees are odd — far more than the two Euler's theorem allows. So no walk, however clever, can cross every bridge exactly once. This is Euler's actual conclusion: the walk is impossible.

Suppose the eastern $A$–$C$ bridge washes out, leaving six bridges. Now $\deg(A) = 2$ and $\deg(C) = 4$, while $\deg(B) = 3$ and $\deg(D) = 3$ are unchanged: exactly two odd vertices, $B$ and $D$. An Euler trail now exists, for instance

which uses the remaining bridges $BC_1, CA, AD, DC, CB_2, BD$ once each.

Instead of removing a bridge, suppose the city adds new ones to make a circuit possible. All four landmasses are odd, so at least two new bridges are needed (each new bridge can fix the parity of at most two vertices). Adding $A$–$B$ and a second $C$–$D$ bridge does it: $\deg(A) = 4$, $\deg(B) = 4$, $\deg(C) = 6$, $\deg(D) = 4$ — all even, and the graph is still connected, so by Euler's theorem a circuit exists. One is

using all nine bridges, $AC_1, CD_1, DA, AB, BC_1, C D_2, DB, BC_2, CA_2$, exactly once and returning to $A$.

The triangular prism has two triangles $a_1b_1c_1$ and $a_2b_2c_2$ joined by the matching $a_1a_2, b_1b_2, c_1c_2$ — $6$ vertices, $9$ edges, every degree $3$. Going around one triangle, crossing over, and returning around the other gives

using the $6$ edges $a_1b_1, b_1c_1, c_1c_2, c_2b_2, b_2a_2, a_2a_1$ and visiting all $6$ vertices exactly once.

Two triangles $abc$ and $cde$ share only the vertex $c$ (the "bowtie"), giving $\deg(c) = 4$ and all other degrees $2$. Vertex $c$ is a cut vertex: removing it disconnects $\{a,b\}$ from $\{d,e\}$, since those pairs have no other connection. A Hamiltonian cycle, minus any one of its vertices, must leave the rest joined by a single path — but deleting $c$ splits the other four vertices into two disconnected pairs, which no path can do. So the bowtie has no Hamiltonian cycle, even though every vertex has degree $\ge 2$.

Split $7$ vertices into $L = \{l_1,l_2,l_3\}$ and $R = \{r_1,\ldots,r_4\}$, joined by all $12$ possible edges between the two sides (none within a side) — the complete bipartite graph $K_{3,4}$. Every edge crosses between $L$ and $R$, so any cycle must alternate sides, $L, R, L, R, \ldots$, and alternating sides forces the cycle to have even length. A Hamiltonian cycle here would need length $7$ (all $7$ vertices), which is odd — impossible. So $K_{3,4}$, despite every vertex having degree $3$ or more, has no Hamiltonian cycle; the obstruction is the unequal split $3 \ne 4$, not a shortage of edges.

Take $6$ vertices $1,\ldots,6$ and join every pair except the three "opposite" pairs $(1,4), (2,5), (3,6)$ — the octahedron graph, $12$ edges. Every vertex is missing only its one opposite, so $\deg(v) = 6 - 1 - 1 = 4$ for all $v$, and $n/2 = 3$: Dirac's condition holds. Indeed $1\to2\to3\to4\to5\to6\to1$ is a Hamiltonian cycle, since consecutive labels are never $3$ apart (never an opposite pair).

Let $s,t,p,q,r$ be mutually adjacent (a $K_5$), and add one more vertex $x$ joined only to $s$ and $t$ — $6$ vertices, $12$ edges. Then $\deg(x) = 2$, well below $n/2 = 3$, so Dirac's theorem says nothing. But the only non-adjacent pairs are $(x,p), (x,q), (x,r)$, each with degree sum $2 + 4 = 6 = n$: Ore's condition holds for every non-adjacent pair, so a Hamiltonian cycle is guaranteed. One is

using edges $xs, sp, pq, qr, rt, tx$, all present, and visiting all $6$ vertices.

Revisit $K_{3,4}$ ($n = 7$) from the previous section. Its only non-adjacent pairs sit within a single side. Two vertices on the $3$-side have degree sum $4 + 4 = 8 \ge 7$: fine. But two vertices on the $4$-side have degree sum $3 + 3 = 6 < 7$: this pair violates Ore's hypothesis, so the theorem simply does not apply — it neither confirms nor (on its own) rules out a Hamiltonian cycle. The direct parity argument from Section 3 is what actually proves $K_{3,4}$ has none; Ore's theorem only explains why no density argument could have shortcut that proof.

The cube graph $Q_3$ has $8$ vertices (the $3$-bit strings), each of degree $3$ (flip any one of $3$ bits), $12$ edges. Building from $G(2) = 00, 01, 11, 10$ by the reflect-and-prefix rule: prefix $0$ to $G(2)$, then prefix $1$ to $G(2)$ reversed ($10, 11, 01, 00$), giving

Each consecutive pair differs in exactly one bit (check $010\to110$: only the leftmost bit changes), and the last, $100$, differs from the first, $000$, in exactly one bit too — a genuine Hamiltonian cycle on $Q_3$.

Apply the same rule once more. Prefixing $0$ to every string of $G(3)$ gives the first $8$ codewords; reversing $G(3)$ to $100, 101, 111, 110, 010, 011, 001, 000$ and prefixing $1$ gives the last $8$:

This lists all $16$ strings of $4$ bits exactly once, consecutive strings always differ in one bit (the rule guarantees it at every step, including the jump from $0100$ to $1100$, which only flips the leftmost bit), and the last, $1000$, differs from the first, $0000$, in one bit as well.