# Prove/disprove: In a graph with at least one component that does not contain a hamilton circuit, we can make it hamiltorian by adding a vertex

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.

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?

-
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

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).

-
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