Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Suppose there is a graph $G$. The graph will either have hamiltonian path or not.

I want to make an expansion $H$ of $G$ by adding nodes (vertexes) and corresponding edges to $G$ so that if a hamiltonian path of $G$ exists, the number of hamiltonian paths of $H$ is odd. If hamiltonian path of $G$ does not exist, $H$ should not have any hamiltonian path.

What would be a way to do this? Is this possible? How many nodes are required to do this?

Edit: when adding new edges, these edges must have an endpoint that is a new vertex(node).

Edit: Obviously, I am not asking for a way that requried trying every case (and checking whether the number of hampath is even or odd) - I want a way that does not require checking of the number of hampaths in the original graph and does not requrie trying every case as aforementioned.

Edit: If every undirected graph has even number of hampaths (except when it has no hampath), directed grpahs(digraphs) are fine. Anyway, even if the graph $G$ is undirected, the expansion can be directed. So, what about digraphs? Is this true?

share|cite|improve this question
Is $G$ a digraph? – Fixee Nov 4 '12 at 2:35
Digraph is fine, but I would prefer undirected graph. – Dotto Nov 4 '12 at 2:39
I think if $G$ is undirected, and if we define a hamiltonian path as a permutation of the vertices, then there are always an even number of such permutations if the number of vertices > 1. – Fixee Nov 4 '12 at 2:41

Your Answer


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

Browse other questions tagged or ask your own question.