Articles of hamiltonian path

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

Prove that every $8$-regular graph has $4$- and $2$-regular spanning subgraphs. Note: A graph is spanning subgraph, if it contains every vertex of the original graph. Furthermore this example’s from Hamiltonian cycle/path topic.

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it’s indeterminable with minimal information: A graph has 17 vertices and 129 edges. Hamiltonian graphs are proved by, as long as the vertices are greater than or equal to 3 (which this is), then if the sum of […]

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 this question. Now, I can see why I need to show the upper bound – for $t(n,H_n) > \binom{n-1}{2} + 1$ […]

Prove $P_m X P_n$ is Hamiltonian if and only if at least one of $m,n$ is even

How to prove “Prove $P_m X P_n$ (graph cartesian product) is Hamiltonian if and only if at least one of $m,n$ is even” Graph cartesian product is Grid graph, if I figure out $P_2 X P_2$ it will be $C_4$ (it is Hamiltonian). How to state this prove ?

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 choose a degree sequence of $(2,2,2,2,2,2)$ and have $C_6$, which has a Hamiltonian path, and two disjoint 3-cycles, which are non-Hamiltonian. How […]

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 work) to indicate that a graph has no Hamilton cycle. a. Show that if m and n are odd integers (not both = 1), […]

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 two non-adjacent vertices is $\geq n$, then I’d be done. Likewise, if I could show that the above […]

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?

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, if the last square is a knight’s move away from the first, and acyclic otherwise. There are several […]