Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


Prove a simple graph $G$ is Hamiltonian if and only if its closure is Hamiltonian.

$|V(G)|=n$, $\deg(u)+\deg(v)\ge n$ ($u$ and $v$ is a pair of non-adjacent vertices on $G$)

I know if $G$ is Hamiltonian, its closure must be Hamiltonian.

However, I don't know how to prove $G$ is Hamiltonian when its closure is Hamiltonian.

I got stuck! Any ideas?

Quote from Scott's reply:
"Suppose that $x_i$ is adjacent to $u$ that if $x_{i+1}$ were adjacent to $v$ in $G_k$, we could modify $C$ to get a Hamilton circuit in $G_k$. "

                |             | 
v--x2--x3--...--xi  xi+1--..--u 

The word is really important, so I drew the diagram and hope it is useful for someone.
Also from the diagram, we can understand why it supposes $x_{i+1}$ is adjacent to $v$ instead of $x_i$.

share|cite|improve this question
Do you mean transitive closure? – dtldarek Apr 7 '12 at 20:02
@dtldarek: From Wikipedia: Given a graph $G$ with $n$ vertices, the closure $\operatorname{cl}(G)$ is uniquely constructed from $G$ by repeatedly adding a new edge $uv$ connecting a nonadjacent pair of vertices $u$ and $v$ with $\deg(v)+\deg(u)\ge n$ until no more pairs with this property can be found. This appears to be the closure that Matt intends. – Brian M. Scott Apr 7 '12 at 21:38
up vote 1 down vote accepted

Consider the construction of $\operatorname{cl}(G)$ from $G$. At each stage you add an edge $uv$ such that $\deg(u)+\deg(v)\ge n$. Say the stages are $G_0=G,G_1,\dots,G_m=\operatorname{cl}(G)$. Show that if $G_{k+1}$ is Hamiltonian, then so is $G_k$. Then from the hypothesis that $\operatorname{cl}(G)$ is Hamiltonian it will follow that $G_{m-1},G_{m-2},\dots,G_0=G$ are all Hamiltonian, and in particular that $G$ is Hamiltonian.

To get you started, suppose that $G_{k+1}$ is Hamiltonian, with Hamilton circuit $C$, and $G_k$ is not Hamiltonian. Let $uv$ be the edge added to get $G_{k+1}$ from $G_k$; clearly $C$ must include $uv$. Say $C$ is $v,x_2,x_3,\dots,x_{n-1},u$, where $x_2,\dots,x_{n-1}$ are the other $n-2$ vertices of $G$.

  1. Suppose that $x_i$ is adjacent to $u$ in $G_k$ for some $i<n-1$; show that if $x_{i+1}$ were adjacent to $v$ in $G_k$, we could modify $C$ to get a Hamilton circuit in $G_k$. Thus, if $x_i$ is adjacent to $u$, $x_{i+1}$ cannot be adjacent to $v$.

  2. Use (1) to show that $\deg_{G_k}(u)+\deg_{G_k}(v)<n$ and so derive a contradiction.

share|cite|improve this answer

Case 1: If G is non Hamiltonian adding any extra edge without loss of any generality we get a maximal non Hamiltonian graph(by definition of maximal non Hamiltonian graph) then graph G is Hamiltonian. Case 2:If possible suppose graph is non-Hamiltonian. If there is path passing through every vertex of G $ V_1 \rightarrow V_2\rightarrow......V_i\rightarrow.....V_n $ $ V_1$&$V_n$ are not adjacent by hypothesis $deg(u)+deg(v) \geq n\\ \\ \\ \\ \\$ $\exists$ some i $V_1$ and adjacent to $V_i$ and $V_n$ adjacent to $V_{i-1}$ this produce a Hamiltonian cycle as follows: $V_1 \rightarrow V_2 \rightarrow....V_i \rightarrow V_{i+1} \rightarrow.....V_n \rightarrow V_{i-1} \rightarrow....V_1$ Which is contradiction.

$\therefore$Our supposition is wrong

$\therefore$ Graph G is Hamiltonian

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.