Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hamiltonian-path]

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

20
votes
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, ...
12
votes
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.) ...
5
votes
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 ...
1
vote
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 (...
8
votes
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.
2
votes
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?
6
votes
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 ...
2
votes
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 ...
2
votes
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}}$ ...
1
vote
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 ...
1
vote
1answer
403 views

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 $...
6
votes
1answer
6k views

Proof of Hamilton Cycle in a Complete Bipartite Graph

For a complete Bipartite graph K(m,n) has a Hamilton cycle if and only if m=n. I want to know if the following proof technique is correct. My proof will consider using proof by contradiction. Assume ...
3
votes
0answers
144 views

How to generate a Penrose tessellation around a given tile?

Given a starting Penrose tile, I need to build a "spiraling" tessellation around it. The following picture illustrates the request: In this example, the starting tile is a "thin rhombus" (the pink ...
1
vote
1answer
69 views

How to convert a maximal planar graph to a regular planar multigraph?

Given a maximal planar graph (coming from the convex hull of a set of points on a sphere), I want to add edges until it is regular (all vertices touch the same number of edges), while keeping it ...
4
votes
3answers
1k views

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. ...
2
votes
1answer
192 views

Spiral path on a Penrose tiling

I would like to color a Penrose tiling by following a "spiral path", painting each tile according to a given color sequence. In this picture, I illustrate what I am looking for: The dashed line ...
2
votes
1answer
2k views

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

I would like to show the following: Show that if a regular graph with degree 3 has a Hamiltonian cycle, then it has an edge colouring with three colours. Is it correct to use the following ...
0
votes
1answer
460 views

Probability of choosing a graph with Hamiltonian cycle

Given $N$ labeled points in a plane one can construct $2^{N(N-1)/2}$ graphs(Unweighted, undirected) with them. Is there any theorem that gives the probability of choosing at random from these a graph ...
7
votes
1answer
162 views

Is there a name for graphs with the following property?

The property of the graph is the following: For any vertex, there is a hamiltonian path starting with this vertex, but the graph is not hamiltonian. The following graph is a small example: Important ...
6
votes
0answers
131 views

Is there a relationship between local prime gaps and cyclical graphs?

By defining the following algorithm I was able to generate some interesting graphs using the values of the gaps between consecutive primes: Start in any prime $p_i$, this will be the initial ...
5
votes
1answer
133 views

Provable Hamiltonian Subclass of Barnette Graphs

Given a bicubic planar graph consisting of faces with degree $4$ and $6$, so called Barnette graphs. We can show that there are exactly six squares. Kundor and I found six types of arrangements of the ...
2
votes
1answer
3k views

Prove Dirac's Theorem by induction on the number of vertices

Dirac's Theorem says: If a connected graph $G$ has $n \ge 3$ vertices and $\delta(G) \ge \frac{n}{2}$, then $G$ is Hamiltonian. Now I want to prove this theorem by induction on $n$. For $i=3$,...
2
votes
2answers
909 views

Clarifying Dirac's theorem

Theorem : If $G$ is a simple graph with $n$ vertices with $ n ≥ 3$ such that the degree of every vertex in G is at least $ n/2$, then $G$ has a Hamilton circuit. In this if $n$ is odd, should I ...
1
vote
0answers
82 views

A contradictory relation between probability and number of paths

Consider an urn containing $c$ balls, $\alpha$ of which are red, $\beta$ of which are blue, and $\gamma$ of which are green, and $\alpha+\beta+\gamma=c$. We perform $n$ trials with replacement of one ...
1
vote
2answers
293 views

Prove that $G$ with 21 vertices with at least 200 edges is Hamiltonian

I'm stuck with this question. 1. Let G be a simple graph on 21 vertices with at least 200 edges. Show that G is Hamiltonian. I tried to use Dirac's theorem to prove it but it is inconclusive because ...
1
vote
1answer
2k views

The number of Hamiltonian cycles in the complete bipartite graph

I know that in the complete bipartite graph $K_{n,n}$ , there is $\frac{n!(n-1)!}{2}$ or $n!(n-1)!$ Hamilton cycles. wiki says first, wolfram says the second one. I know that there is $2n$ ways to ...
0
votes
1answer
190 views

How many Hamiltonian cycles are there in a complete graph that must contain certain edges?

Consider a complete graph $G$ that has $n \geq 4$ vertices. Each vertex in this graph is indexed $[n]=\{1,2,3, \dots n\}$ In this context, a Hamiltonian cycle is defined solely by the collection of ...
0
votes
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 ...
-1
votes
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, ...