Skip to main content

Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
23 votes
5 answers
26k 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.) ...
a1234's user avatar
  • 233
3 votes
4 answers
2k views

Generate all de Bruijn sequences

There are several methods to generate a de Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length $n$...
qwr's user avatar
  • 10.8k
1 vote
3 answers
2k views

A $3 \times 3 \times 3$ cube has no Hamiltonian path starting at the corner.

We have a $3\times3\times 3$ cube which has $27$ cubes each $1\times1\times1$ stuck together as usual. $2$ cubes are neighbours if they have a common face. The corner cubes are the $8$ cubes at the ...
Katrina's user avatar
  • 11
9 votes
4 answers
11k 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 ...
Pavel's user avatar
  • 1,552
3 votes
3 answers
19k 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?
Krishnaprasad's user avatar
2 votes
3 answers
632 views

Induction on grid Hamiltonian graph

This exercise is thaken from [1]: 1.7 A rook’s tour. Let $G$ be an $m \times n$ grid—that is, a graph with $m n$ vertices arranged in an $m \times n$ rectangle, with each vertex connected to its ...
incud's user avatar
  • 107
3 votes
1 answer
9k 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 ...
BrianR's user avatar
  • 43
2 votes
1 answer
892 views

Graph with even vertices and ${n-1}\choose 2$ $+ 1$ edges has a perfect matching

Let G be a simple graph with an even number n of vertices and suppose that G has at least $n-1\choose 2 $$+ 1$ edges. Prove that G has a perfect matching. I tried to use induction but I am ...
Kosovo Buda's user avatar
1 vote
1 answer
682 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 (...
M. Red's user avatar
  • 350
25 votes
3 answers
10k 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, ...
Charles Stewart's user avatar
9 votes
1 answer
1k 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.
user12344567's user avatar
6 votes
3 answers
8k 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 ...
user avatar
5 votes
2 answers
3k 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}}$ ...
Dorgham's user avatar
  • 378
5 votes
1 answer
2k views

A bipartite graph like $G(X,Y)$ such that $|X|=|Y|=k$ and $\delta(G) \gt \frac {k}{2}$ is Hamiltonian.

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets $X$ and $Y$ (that is, $X$ and $Y$ are each independent sets) such that every edge connects a vertex in $X$...
Arman Malekzadeh's user avatar
5 votes
1 answer
787 views

Definition of a separating triangle in planar graph

In Bill Tutte's famous book Graph Theory as I Have Known It he discusses Hassler Whitney's theorem on Hamiltonian cycles in planar graphs, summarising it thus: Any strict triangulation in which there ...
HughHughTeotl's user avatar
4 votes
3 answers
606 views

Difficulty in understanding the proof of Petersen Graph is non hamiltonian as given in graph theory text by Chartrand and Zhang

I was going through the text : A First Course in Graph Theory by Chartrand and Zhang where I could not understand a few statements in the proof. Below is the excerpt: Theorem 6.4 : Petersen graph is ...
Abhishek Ghosh's user avatar
3 votes
2 answers
703 views

Define A Graph - Tree Graph With "Cycles" as Nodes

I am working on my thesis and I would like to have a proper definition for this type of graph: "Tree Graph With Nodes As Cycles" I would like to define a graph similar to a "simple tree", but some of ...
John's user avatar
  • 103
2 votes
1 answer
957 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 $...
Roeny's user avatar
  • 113
2 votes
2 answers
5k 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 ...
user3704516's user avatar
2 votes
1 answer
3k views

If $deg(u)+deg(v) \ge n-1$ for $u$ and $v$ are non adjacent vertices, then G has Hamiltonian path

Hamiltonian path is a path that contains all of the vertices of the graph. I know that if $deg(u)+deg(v) \ge n$ for every two non adjacent vertices $u$ and $v$ then the graph has Hamiltonian cycle and ...
James's user avatar
  • 159
1 vote
1 answer
1k views

Hamiltonian path exists if each two nonadjacent vertices has sum of degrees equal to n-1

Here is a question from a textbook I’m reading, prove that a simple graph with n vertices has a hamiltonian path if the sum of degree number of each two none adjacent vertices is n-1. I know A graph ...
Negar Rezaei Nejad's user avatar
12 votes
2 answers
2k views

Can a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle?

Can a bipartite graph with at least three vertices have the following properties simultaneously: Every vertex is the initial vertex of some Hamiltonian path. The graph contains no Hamiltonian cycle. ...
Peter's user avatar
  • 84.8k
10 votes
0 answers
584 views

The number of Hamiltonian paths in a tournament is always odd?

A tournament is defined as an orientation of a complete graph. Prove or disprove the following statement: In a tournament, there are exactly an odd number of Hamiltonian paths. In all cases I’ve ...
Juggler's user avatar
  • 1,343
7 votes
1 answer
213 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 ...
Peter's user avatar
  • 84.8k
6 votes
0 answers
173 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 ...
iadvd's user avatar
  • 8,905
6 votes
1 answer
971 views

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

Is there an example of a simple, undirected graph with all vertices having degree 3 or greater that doesn't have a hamiltonian path? I've seen this question appear in the title of this post, but then ...
Steverino 4086's user avatar
5 votes
1 answer
695 views

Does every regular, bipartite graph contain a Hamiltonian path?

This may be a rather straight-forward question; however, I am unable to arrive at an answer myself. Given a $r$-regular, $k$-edge-connected, bipartite graph, will there always be a Hamiltonian path in ...
sugohugo's user avatar
5 votes
1 answer
1k views

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 ...
Botond Kiss's user avatar
5 votes
1 answer
227 views

Length of shortest hamiltonian path in a circle

Let's say I have a circle of radius $r$. I will place $N$ points inside this circle, and then find the shortest hamiltonian path going through all these points. Of course, I know that this shortest ...
rambi's user avatar
  • 215
5 votes
3 answers
2k 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. ...
user2494584's user avatar
5 votes
1 answer
152 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 ...
draks ...'s user avatar
  • 18.5k
4 votes
1 answer
7k 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 ...
Artem's user avatar
  • 1,208
3 votes
0 answers
400 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 ...
user avatar
3 votes
2 answers
613 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 ...
user avatar
3 votes
1 answer
498 views

Prove a lower limit of $|E(G)|$ where for any $u,v\in G$, there exists a Hamilton path

Define a "Hamilton-connected graph $G$" as For any vertices $u, v \in G$, a Hamilton path exists, where the two ends of the path are vertices $u$ and $v$. Try to prove that if $G$ is a Hamilton-...
iBug's user avatar
  • 399
3 votes
2 answers
2k 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 ...
Heisenberg's user avatar
  • 3,237
3 votes
1 answer
5k 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$,...
Arman Malekzadeh's user avatar
2 votes
2 answers
6k views

Ore's Theorem - Graph Theory

I'm trying to understand Ore's Theorem but it seems I'm a bit confused. "Theorem (Ore; 1960) Let G be a simple graph with n vertices. If $$\operatorname{deg}(v) + \operatorname{deg} (w) ≥ n$$ for ...
Fizzle's user avatar
  • 73
2 votes
1 answer
1k 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 ...
biryani's user avatar
  • 573
2 votes
3 answers
2k views

prove that a graph with p vertices and $2+(p-1)(p-2)/2$ edges is hamiltonian

A Hamiltonian graph is a graph which has a Hamiltonian cycle. A Hamiltonian cycle is a cycle which crosses all of the vertices of a graph. According to Ore's theorem , if $p \ge 3$ we have this : ...
Arman Malekzadeh's user avatar
2 votes
1 answer
544 views

A graph that is tough but not Hamiltonian.

A graph G is tough if the number of $c(G-s) \le |S|$ for all $S \in V(G)$. And I read that every tough graph is Hamiltonian, but the other way is not true. I was wondering if there is an example of ...
iraj's user avatar
  • 33
1 vote
3 answers
6k views

Graph Theory: How do we know Hamiltonian Path exists in graph where every vertex has degree ≥3?

I am trying to prove that if every node of a graph G has degree of at least 3 then G contains a cycle and a chord. My current approach is as follows: Separate the graph G into connected components ...
Kvass's user avatar
  • 367
1 vote
1 answer
325 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 ...
DPKR's user avatar
  • 211
1 vote
1 answer
506 views

Prove that if G is hamiltonian then Line graph of G is hamiltonian too [duplicate]

Prove that if G is hamiltonian then Line graph of G is hamiltonian too I know that we have a closed path with all vertices included then because every edge in this path is connected to two other edges ...
Newbiemathlover's user avatar
1 vote
1 answer
762 views

Question about closed knight's tours for n x m chessboard

Is there a simple mathematical algorithm where you can get a CLOSED knight' tour on an n x m chessboard? I need a way to prove that it is mathematically possible or impossible to have a closed knight'...
Arale's user avatar
  • 181
1 vote
0 answers
90 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 ...
user avatar
1 vote
2 answers
530 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 ...
John Graig's user avatar
1 vote
1 answer
89 views

double tours embedding of nonhamiltonian bicubic graphs

Can Georges Graph (or any other nonhamiltonian bicubic graph ) be embedded on an oriented surface of genus -2, i.e. a double torus? If it helps, it would have $F=E+\chi-V=75-2-50=23$ faces...
draks ...'s user avatar
  • 18.5k
1 vote
1 answer
3k views

Showing that a graph doesn't contain a hamiltonian path

In class, we learnt a method that helps us to show that there is no hamiltonian path (resp. cycle) in a graph. For the graph (on the right side, it reads "$19$ vertices" and "$33$ edges") it works ...
Julian 's user avatar
  • 1,411
1 vote
1 answer
3k views

Number of Hamiltonian Cycles in Kn,n

Suppose $K_{n,n}$ is a complete bipartite graph with vertices on left and right indexed by {${l_1, l_2, ..., l_n}$} and {$r_1, r_2, ..., r_n$} for $n \geq 3$. I would like to ask how many ...
Anastazia Nichole's user avatar