[Solved]: r-regular graph and hamiltonian path

Problem Detail: 

I am having some issues proving a problem I am working on. I have been sketching out examples but the proof is not jumping out at me.

Question: Let $G = (V,E)$ be an undirected $r$-regular graph (that is each vertex has a degree of $r$) for some $0 < r < n$, where $|V| = n > 1$. Prove that either $G$ or its complement $G^*$ has a hamiltonian path.

Now the reason it's asking for $G$ or $G^*$ is because if it's not a connected undirected graph then taking the complement will make it connected.

So lets assume that it's a connected $r$-regular graph. We start at a vertex $v$. From this vertex we can visit up to $r$ adjacent vertices. So we visit one of them, say $u$, and from there we have $r-1$ vertices to choose from because we do not want to go back to vertex $v$.

Now I am trying to formulate a proof by going from vertex to vertex until all vertices are visited exactly once (hamiltonian path). But I do not see how to formulate the proof. Somehow each new vertex I visit will always have an uninformed neighbour until I reach the final vertex on the path.

Am I on the right track?

Asked By : gprime

Answered By : svinja

You are underselling the "G or G*" part. This suggests a proof of the form:

• "assume G isn't Hamiltonian ... prove G* must be". So try that route.

To give a further hint, I remind you of the Dirac theorem:

• If a connected graph G has n >= 3 vertices and the degree of each vertex is at least n/2, then G has a Hamiltonian cycle (if it has a cycle, obviously it also has a path, you just remove an edge from the cycle).

• Additionally, an n-vertex r-regular graph with r >= n/2 must be connected (assume it is not connected - what is the minimum number of vertices each connected component must have? Can there be more than 1 such component?)

I think these should give you the idea how to prove it for n >= 3.

Then it just remains to prove it for n = 2, which is trivial (the only reason it isn't included in above theorem is that it only has a path, not a cycle).

Note: because I am not sure a complement is even defined on a non-simple graph, I am assuming G is simple. But if it wasn't, the statement-to-prove couldn't be true, even if you defined a complement in any way that makes sense - what would be the complement of this graph, and how could either have a Hamiltonian path:

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12916