Continuing with my studies in Introduction to Graph Theory 5th Edition by Robin J Wilson, one of the exercises asked to prove that, if $G$ is a bipartite graph with an odd number of vertices, then $G$ is non-Hamiltonian. This is what I've come up with. Is it strong enough?

Let graph $G$ be a bipartite graph with an odd number of vertices and G be Hamiltonian, meaning that there is a directed cycle that includes every vertex of $G$ (Wilson 48). As such, there exists a cycle in G would of odd length. However, by Theorem 2.1, a graph $G$ is bipartite if and only if every cycle of $G$ has even length (Wilson 33). Proven by contradiction, if $G$ is a bipartite graph with an odd number of vertices, then $G$ is non-Hamiltonian.

As an example, the picture below has 13 vertices so it must be non-Hamiltonian.

enter image description here

  • 2
    $\begingroup$ Yes, this is correct. $\endgroup$ – Brian M. Scott Dec 14 '16 at 21:41
  • 1
    $\begingroup$ So the picture I just added in, as an example, has 13 vertices so that must be non-Hamiltonian as I just proved. $\endgroup$ – Learner Dec 14 '16 at 21:53

Yes, your proof is quite correct.

  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review $\endgroup$ – I am Back Dec 15 '16 at 16:53
  • $\begingroup$ @THELONEWOLF. the OP's question is whether or not their proof is correct. It is correct. I don't think there is a more appropriate answer than this, and I would rather this question not be added to the Unanswered Question queue. $\endgroup$ – Mike Pierce Dec 15 '16 at 17:03
  • $\begingroup$ I have talked more than 10 experienced users on the site and everybody agree on one thing which is that avoid answers/comment which are unnecessary. I think that this answer is unnecessary, it is a good comment but a bad answer. Regards $\endgroup$ – I am Back Dec 15 '16 at 17:07

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.