# Questions tagged [hamiltonian-path]

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

601 questions
Filter by
Sorted by
Tagged with
41 views

### Why is it true that a connected graph with 500 vertices and 5000 edges does not have a Hamiltonian Cycle? [closed]

Why is it true that a connected graph with 500 vertices and 5000 edges does not have a Hamiltonian Cycle? How are you able to tell? Is this related to some theorem? I know that a Hamiltonian cycle ...
19 views

### Finding path lengths by the power of adjacency matrix of an undirected graph

The same question was asked almost 7 years ago. It turned out to be a matter of terminology in different textbooks between the terms "path" and "walk". While the answers addressed ...
• 103
1 vote
33 views

### Maximum number of edges in a connected graph without Hamiltonian path

What is the maximum number of edges in a connected graph without Hamiltonian path? I've searched the Internet on a while, and read the question Maximum number of edges in a non-Hamiltonian graph here,...
1 vote
49 views

### Hamiltonian paths in same degree graph

Suppose we have a connected graph, and all vertices of this graph have the same even degree. Is it always true that this graph has a Hamiltonian path? Furthermore, is it true if the degree $2k$, this ...
• 13
1 vote
26 views

### A Hamiltonian cycles (plural) problem?

I'll be brief. I have a set of n vertices in a complete weighted graph, some of these vertices can be thought of as power plants and the rest as cities, and I need to find the shortest way to connect ...
82 views

### Proof that $n$ points on a plane cannot be connected with straight lines under a certain angle treshold

I have $n$ points on a two-dimensional coordinate plane. My goal is finding a path that visits every point once, with straight lines interconnection two points. Additionally, the angle of a line ...
• 35
1 vote
20 views

• 2,856
23 views

### Topological sort in tournament graph to find hamiltonian path

Suppose $G(V,E)$ is a tournament graph with directed edges. It has $n$ vertices and $\binom{n}{2}$ directed edges. An edge $uv$ means that $u$ beat $v$ in the graph. I proved that the graph has a ...
1 vote
28 views

### What kind of graph is this? Hamiltonian by association?

Here is an example of a connected cycle using the edges: $ABC-BCD-BCE-CDE-BDE-ABE-ACE-ADE-ACD$ Here $ABC$ shares $BC$ with $BCD$, $BCD$ shares $BC$ with $BCE$, ... , $ACD$ shares $AC$ with $ABC$. ...
• 505
29 views

### What does it mean by 'preassigned orientation'?

I want to solve the next exercise of graph theory: Prove that a transitive tournament contains a Hamilton path with any preassigned orientation My problem is that I don't understand what the exercise ...
• 325
1 vote
38 views

### Is a subdivision of a Hamilton Graph, a Hamilton Graph too?

How would I go about showing this? I think the answer is yes, as subdividing a graph doesn't affect the cycles it has: When going from node a to b, a subdivision of 1 will for example simply make you ...
154 views

### Prove that there is a Hamiltonian path in the complete bipartite graph $K_{m,n}$ if and only if $|n-m| \leq 1$

The main concept of this question has to do with Paths in the Complete Bipartite Graph. First I have proven that assuming $n \geq m \geq 1$, $K_{m,n}$ has at most $2m+1$ vertices. The main point to ...
40 views

### Conversion of SDP relaxation of Travelling Salesman Problem (TSP) to standard SDP form

The standard SDP formulation is given as : \begin{equation} \begin{aligned} \min_{X\in H^{n}} \quad& \langle X,M_{0} \rangle\\ \textrm{s.t.} \quad& l_{s} \leq \langle X, M_{s} \rangle \leq ...
189 views

### Prove that if a tournament $T$ contains a cycle, then it contains two Hamiltonian paths

Prove that if a tournament $T$ contains a cycle, then it contains two Hamiltonian paths. How can I prove that, I thought that since $T$ is a tournament it has a Hamiltonian path $P$, and since an ...
418 views

There are 10 cities in a country. The Government starts to build direct roads between the cities, but with random access, it can build direct road between two cities even if there is already another ...
• 21
104 views

### Hamilton cycle on chessboard

Suppose we have $8 \times 8$ chessboard such that two squares are adjacent iff they share a common side. In one move pawn can move to adjacent square. Prove that the pawn made a different number of ...
• 89
15 views

### What is the time complexity to finding the least weight for Hamiltonian cycle in complete graph without finding best tour?

As we know finding the best tour in complete graph with n nodes, or the Traveling Salesperson Problem solved by the dynamic programming algorithm in $n^2.2^n$ time ...
• 619
49 views

### An extension of Dirac Theorem

Following a related proof of Dirac theorem, I want to show that if $G$ is a balanced bipartite graph of order $n$ with minimum degree more than $n/4$, then $G$ has a Hamilton cycle. Dirac's theorem: ...
• 701
1 vote
70 views

### What is the necessary and sufficient condition for a graph to be a Hamiltonian Chordal Graphs?

Chordal Graph. A chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Hamiltonian ...
• 1,272
I have two sets of points in $\mathbb{R}^2$, let's call them red and blue. I would like to create a Hamiltonian Cycle, i.e., cycle going through all points once. This cycle should minimise the ...