0
$\begingroup$

Prove that a graph that posses a Hamiltonian circuit must have no pendant vertices.

To prove this, each vertex in a graph, that also has a hamiltonian circuit, much acquire at least two edges in order for the graph to start and end at the same vertex and visit every vertex once with no repeats. Therefore the graph must have no pendant vertices.

Is that correct?

$\endgroup$
0
$\begingroup$

Yes, this is correct. In a Hamiltonian graph each vertex $v$ is incident to two edges from the cycle so its degree is at least $2$, so $v$ is not a pendant vertex.

$\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.