# Questions tagged [hamiltonian-path]

A path in a graph that visits each vertex exactly once.

29 questions
3answers
6k views

### How many knight's tours are there?

The knight's tour is a sequence of 64 squares on a chess board, where each square is visted once, and each subsequent square can be reached from the previous by a knight's move. Tours can be cyclic, ...
1answer
9k views

### Prove that every tournament contains at least one Hamiltonian path.

A tournament is a directed graph with exactly one edge between every pair of vertices. (So for each pair (u,v) of vertices, either the edge from u to v or from v to u exists, but not both.) ...
4answers
5k views

### Maximum number of edges in a non-Hamiltonian graph

I need to show that the maximum number of edges of non-Hamiltonian, simple graph, on $n$ vertices noted by $t(n,H_n)$ is $\binom{n-1}{2} + 1$. It's essential to show the upper and lower bounds for ...
1answer
326 views

### Connected graph with colored edges

We have connected undirected graph with colored edges in two way (green or blue). And also each vertex have the same number of green and blue edges. How to prove that there are alternate colored (...
1answer
678 views

### Does every connected $r$-regular bipartite graph contain a Hamiltonian cycle?

Here's a quickie: Let $r\ge2$. Does every connected $r$-regular bipartite graph contain a Hamiltonian cycle? I've been playing around with this for almost an hour, but I can't prove it.
3answers
7k views

### Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.

In a complete graph with $n$ vertices there are $\frac{n−1}{2}$ edge-disjoint Hamiltonian cycles if $n$ is an odd number and $n\ge 3$. What if $n$ is an even number?
3answers
4k views

### Proving that a graph of a certain size is Hamiltonian

For any graph with order $n \geq 3$, given that its size is $$m \geq \frac{\left(n-1\right)(n-2)}{2} + 2,$$ show that the graph is Hamiltonian. I know that if I can show that the degree sum of any ...
2answers
1k views

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

It is generally difficult to determine whether a (large) graph have no Hamilton cycle (As opposed to determining whether it has any Euler circuit). This example illustrates a method (which sometimes ...
2answers
451 views

### Expected number of hamiltonian paths in a tournament

The following theorem is from Alon&Spencer's The probabilistic method, in the beginning of chapter 2: Theorem 2.1.1: There is a tournament $T$ with $n$ vertices and at least $\frac{n!}{2^{n-1}}$ ...
2answers
784 views

### Hamiltonian and non-Hamiltonian connected graph using the same degree sequence

I'm trying to find out if it is possible to construct a connected Hamiltonian and a connected non-Hamiltonian graph using the same degree sequence. For disconnected graphs it would be easier, I could ...
1answer
403 views

1answer
551 views

### dirac's theorem not work

I am studing graph theory specifically hamiltonian cycles I have a doubt with a exercise, it is a connected simple graph with 13 vertices, the book says that this graph has a hamilton cycle(truly it ...
1answer
250 views

### hamiltonian cycle need assistance [duplicate]

so I'm trying to complete this question for uni and am stuck. show that G = (V, E) has no Hamiltonian cycle, where the vertices are V = {a, b, c, d, e, f, g} and the edges are E = {ab, ac, ad, bc, ...