# Tag Info

### 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 ...
• 159k

### (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 ...
• 15.3k
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 ...
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 ...
• 104k
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 ...
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.
• 156
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 ...
• 402

### Playing Doublets with the Primes

I can confirm that the corresponding graph is connected. Moreover, it has a hamiltonian cycle:

### 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 ...
• 104k

### 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 &...
• 257

### 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 ...
• 144k

### 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 ...
• 4,122
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-...
• 398
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 ...
• 41.3k
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 ...
• 104k
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 ...
• 9,026
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, ...
• 144k
Accepted

• 63.4k
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 ...
• 101k
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–...
• 10.8k

### 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 ...
• 493
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 ...