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

Prove/disprove: In a graph $G$ with at least one component that does not contain a Hamiltonian circuit, we can add a vertex $x$ and certain edges that connect it with certain vertices in the graph, such that we get a graph where every component of the graph has a Hamiltonian circuit.

My answer was:

Disprove. Take for example the claw graph with 3 vertices. Any addition of $x$ and certain edges will not make a Hamiltonian circuit. (it does make a Hamiltonian path, but not a circuit.)

Is that correct or am I missing something?

share|cite|improve this question
If by "claw graph with 3 vertices" you mean K(1,2), then you can indeed make a Hamiltonian cycle. Are you thinking Eulerian cycle maybe? – gogurt Jun 7 '13 at 13:44
Yes I mean $K(1,3)$. How can I make a Hamiltonian cycle in $K(1,3)$? – TheNotMe Jun 7 '13 at 13:46
Oops, hit the wrong key, sorry; I meant K(1,2). My mistake. See the answer below. – gogurt Jun 7 '13 at 13:48
up vote 2 down vote accepted

I don't know what you mean by "claw graph with 3 vertices". If you mean $P_3$ or $K_{1,2}$, then indeed we can make a Hamiltonian circuit, by creating a square. If you mean $K_{1,3}$, then your example is correct but your proof is incomplete. It can only help (in terms of producing a Hamiltonian circuit) to connect $x$ to every vertex in $K_{1,3}$. Consider the three vertices of degree 2 that result. Each path from one to another must pass through either $x$ or the other vertex of degree 4. But in a Hamiltonian circuit one needs to be able to get from each to the next (three paths) that do not intersect. Contradiction.

Specific errors/omissions in OP's solution:

  1. Does not discuss which edges are added to $x$, except for the general and unsupported claim "any".

  2. Does not justify why such an addition will not make a Hamiltonian circuit, or why it will make a Hamiltonian path.

  3. Uses the nonstandard term "claw graph with 3 vertices" for $K_{1,3}$ (which has 4 vertices).

share|cite|improve this answer
Yes I meant $K_{1,3}$. – TheNotMe Jun 7 '13 at 13:47
So my answer is correct? – TheNotMe Jun 7 '13 at 13:48
@TheNotMe It is incomplete... – N. S. Jun 7 '13 at 13:48
Incomplete as in sense of a full mathematical proof? – TheNotMe Jun 7 '13 at 13:50
Easier argument: I am going to denote by $u_1$ respectively $v_1,v_2,v_3$ the vertices of $K_{13}$, Assume there is a Hamiltonian cycle. Then the cycle has $5$ vertices, thus two of the $v_i$'s must be adjacent... – N. S. Jun 7 '13 at 13:51

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.