Skip to main content
45 votes

Is this graph Hamiltonian?

This is a bipartite graph. Colour the three middle vertices red and the other four vertices blue. Each path in the graph has vertices alternating in colour. So any Hamiltonian cycle has an equal ...
Angina Seng's user avatar
15 votes

(Graph Theory) Prove that $H_n$ has a Hamiltonian cycle for $n$ ≥ 2.

Here's one solution: Your graph $H_n$ is an n-dimensional hypercube. For the induction step, separate the cube into two "faces" by cutting along one dimension. Do parallel Hamiltonian cycles on each ...
Yly's user avatar
  • 15.3k
14 votes
Accepted

Does knowing a graph has a Hamiltonian Cycle make it easier to find the cycle?

No (or rather: no, unless P=NP). If it were so, then there would be a concrete polynomial $p$ that bounded the running time of such an algorithm. Therefore you would be able to detect whether a graph ...
hmakholm left over Monica's user avatar
12 votes
Accepted

Show that 3-regular graph (with Hamiltonian cycle) has chromatic index 3

By the handshaking lemma, the 3-regular graph must contain an even number of vertices, so the Hamiltonian cycle must be of even length; colour the edges of this cycle alternating two of the three ...
Parcly Taxel's user avatar
12 votes
Accepted

Is this graph Hamiltonian?

A more verbose explanation of the argument made by Lord Shark the Unknown's answer: This is a bipartite graph (two sets of vertices that form a graph such that no edge places two vertices from the ...
Jochem Kuijpers's user avatar
12 votes
Accepted

What is the difference between a Hamiltonian Path and a Hamiltonian Cycle?

The cycle starts and ends in the same vertex, but the path does not.
Tereza's user avatar
  • 156
11 votes
Accepted

Is every Eulerian graph also Hamiltonian?

It is not the case that every Eulerian graph is also Hamiltonian. It is required that a Hamiltonian cycle visits each vertex of the graph exactly once and that an Eulerian circuit traverses each edge ...
JOF14's user avatar
  • 402
9 votes

Playing Doublets with the Primes

I can confirm that the corresponding graph is connected. Moreover, it has a hamiltonian cycle:
Freddy Barrera's user avatar
9 votes

Zelda - Oracle of Ages tiles rooms puzzles: how can you prove if there are/aren't solutions?

For the "impossible room", recolour the blue squares and yellow goal square black and white in a chessboard pattern, such that the upper-left square is white. Then there is one more white ...
Parcly Taxel's user avatar
8 votes

Hamilton paths/cycles in grid graphs

This is a more formal construction, building off of the answers by Brian M. Scott and David Ongaro. The theorem is actually: an n x m grid graph is Hamiltonian if and only if: A) m or n is even and m &...
Zags's user avatar
  • 257
8 votes

A closed Knight's Tour does not exist on some chessboards

There's a really pretty proof for part (b), which the accepted answer does not do justice to by hiding it under links. We consider two colorings of the $4 \times n$ board. The first is the usual ...
Misha Lavrov's user avatar
7 votes

Prove that every tournament contains at least one Hamiltonian path.

A bit complicated for this problem, but the idea is often useful for other problems. Let $V=\{v_1,v_2,\ldots,v_n\}$ be the set of vertices and $E$ be the set of edges of the graph $G$. Consider all ...
richrow's user avatar
  • 4,122
7 votes
Accepted

1-Factorization of complete Graphs

A 1-factor is a spanning subgraph, while a 1-factorization of $K_n$ is the partition of $K_n$ into multiple 1-factors. In the example given in the question, $K_4$ is partitioned into three 1-...
wto's user avatar
  • 398
7 votes
Accepted

Edge-disjoint Hamiltonian cycles in a planar graph.

Yes. Here is an example on the octahedron. It is easy to see that this is the smallest possible example, since if $G$ has fewer than $6$ vertices, or $6$ vertices with fewer edges, there aren't enough ...
Especially Lime's user avatar
7 votes
Accepted

Where is the proof of Tutte's graph having no Hamiltonian cycles?

Tutte's 1946 paper, "On Hamiltonian circuits" (Journal of the London Mathematical Society, 21 (2), pp. 98–101), began with the pentagonal prism. It is relatively easy to show that no Hamiltonian ...
Parcly Taxel's user avatar
7 votes
Accepted

How to calculate quantity of Hamilton cycles

Just knowing the number of vertices and their degrees isn't enough information to tell the number of Hamiltonian cycles, or even whether the graph has one. The single such graph for $n=2$, and the 16 ...
Nick Matteo's user avatar
  • 9,026
7 votes
Accepted

How does Grinberg's theorem work?

Of course, before we find a Hamiltonian cycle or even know if one exists, we cannot say which faces are inside faces or outside faces. However, if there is a Hamiltonian cycle, then there is some, ...
Misha Lavrov's user avatar
7 votes
Accepted

Arranging Drilled Unit Cubes into a Rectangular Prism Without Breaking the Thread

We label the coordinates of a unit cube vertex by an integer vector $(x, y, z)$. We easily see that an invariant for the vertices visited by the thread is given by $(y-x \text{ mod } 2, z-x \text{ mod ...
caduk's user avatar
  • 4,730
6 votes
Accepted

Who has a winning strategy in the hamilton-circle-game?

Computation over all labeled graphs shows that for $n = 5$ and $n = 6$ the first player has a winning strategy, for $n = 7$ and $n = 8$ hasn't. My actual conjecture is the following: first player has ...
Smylic's user avatar
  • 6,873
6 votes
Accepted

Prove that every 8-regular graph has 4-and 2-regular spanning subgraph!

This is part of a general result called Petersen's 2-factor theorem, which is not too difficult to prove as a whole. Theorem (Petersen): Let $G$ be a $2k$-regular graph. Then $G$ has a decomposition ...
EuYu's user avatar
  • 41.6k
6 votes
Accepted

2-edge-connectivity and Hamiltonian Cycles

Consider the complete bipartite graph $K_{n,n+1}$. This is certainly 2-edge-connected (in fact, I believe it is $n$-edge-connected) but it does not have a Hamiltonian cycle by a parity argument: any ...
Misha Lavrov's user avatar
6 votes

Is there a non-planar, non-hamiltonian and eulerian graph?

Take two copies of $K_5$ and identify one of the nodes in one with one of the nodes in the other.
hmakholm left over Monica's user avatar
6 votes
Accepted

Playing Doublets with the Primes

For the first question the answer is yes, for the second question the answer is 6, To solve the question i used both (Java and Wolfram), the idea is this i made a graph with nodes being the primes ...
Ahmad's user avatar
  • 418
6 votes
Accepted

Do there exist asymmetric hamiltonian graphs?

Yes, there do. Here is an example. Arrange vertices numbered 1 to 7 cyclically, so that 7 connects back to 1. Now add edges (1, 3), (1, 4), (2, 5), (2, 6), (2, 7). Proof that the automorphism group ...
Eric M. Schmidt's user avatar
6 votes

Do there exist asymmetric hamiltonian graphs?

Here is an asymmetric Hamiltonian graph with $6$ vertices and $8$ edges. Start with a $C_6$ graph with vertices $v_0,v_1,v_2,v_3,v_4,v_5$ and edges $v_0v_1,v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_0$. Now ...
bof's user avatar
  • 78.7k
6 votes

Induction on grid Hamiltonian graph

As noted in the comments; coloring the vertices black and white in a chessboard pattern, in any path the colors of the vertices will alternate. So if $m$ and $n$ are both odd, then the color of the $...
Servaes's user avatar
  • 63.4k
6 votes
Accepted

Is there a graph with all vertices having degree 3 or greater that doesn't have a hamiltonian path?

Yes, even if we further restrict (as you probably had in mind) to connected graphs. One example is the complete bipartite graph $K_{3, 5}$, whose partitions have $3$ and $5$ vertices. (In fact, this ...
Travis Willse's user avatar
6 votes
Accepted

Does every $3$-regular bipartite graph have a $4$-cycle?

A counterexample is for example Tutte $12$-cage. The Tutte $12$-cage is a bipartite cubic Hamiltonian graph. The length of its smallest cycle is $12$ (as a $12$-cage). Another example is the Tutte–...
kabenyuk's user avatar
  • 10.8k
5 votes

Prove that every tournament contains at least one Hamiltonian path.

Let T = (V,E) be a tournment. Let P = $w_{1} w_2 \cdots w_{m}$ be a maximum lenght path starting with vertex $w_1$. Let W = $\{ w_{1}, w_2, \cdots, w_{m} \}$ be the set of vertices of path P. Suppose ...
awCwa's user avatar
  • 493
5 votes
Accepted

Show that this graph has no hamiltonian cycle.

Notice that the cycles are even. You can redraw the graph as a bipartite graph with uneven parts ($5$ and $6$). This means that every step is between the two parts, and the fact that the two parts do ...
Joffan's user avatar
  • 39.8k

Only top scored, non community-wiki answers of a minimum length are eligible