1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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