1
$\begingroup$

Show that $ G = (V, E)$ has no Hamiltonian cycle, where the vertices are $ V = \{ a, b, c, d, e, f, g \} $ and the edges are $E = \{ ab, ac, ad, bc, cd, de, dg, df, ef, fg \}$.

From my working out, the vertices $ a, b, c, d, e, f$ are odd degrees of 3 and 1. Moreover $g $ being a even vertices of 2.

There were three points that were made in my textbook to show that a graph does not contain a Hamilton circuit:

  1. A graph with a vertex of degree one cannot have a Hamilton circuit.
  2. Moreover, if a vertex in the graph has degree two, then both edges that are incident with this vertex must be part of any Hamilton circuit.
  3. A Hamilton circuit cannot contain a smaller circuit within it.

According to the definition graph G does not have a Hamiltonian cycle because of the first definition.

However, I am confused about 2 & 3 definitions and I am not sure if this graph involves them or not.

$\endgroup$

closed as off-topic by apnorton, Henrik, user91500, Watson, Daniel W. Farlow Oct 8 '16 at 18:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – apnorton, Henrik, user91500, Watson, Daniel W. Farlow
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Welcome to Mathematics! We like to see questions that show some form of context. This can take the form of showing your work, explaining how you came across the problem, or detailed explanation of what is confusing you. This helps us help you better. $\endgroup$ – apnorton Oct 8 '16 at 4:51
  • 2
    $\begingroup$ 1, 2 and 3 are not definitions. The definition of a Hamilton cycle is a simple cycle passing through every vertex. Those are just examples of things that might prevent a graph from having a Hamilton cycle. Once you've proved that a graph is non-Hamiltonian, there is no need to look for a second and third proof of the same property. $\endgroup$ – Erick Wong Oct 8 '16 at 5:04
  • 1
    $\begingroup$ If you listed the edges correctly then a, c, f have degree 3; b, e, g have degree 2; d has degree 5; and there are no vertices of degree 1. $\endgroup$ – bof Oct 8 '16 at 5:20
  • 2
    $\begingroup$ Possible duplicate of hamiltonian cycle need assistance $\endgroup$ – bof Oct 8 '16 at 8:57
3
$\begingroup$

As discussed in the comments, the three points are not definitions. They are just handy facts you can use to show that a graph is not Hamiltonian. If the facts don't apply to a given graph, it doesn't imply that it is Hamiltonian either - the test is just inconclusive.

Fortunately enough, we can use facts 2 and 3 to prove that the given graph indeed has no Hamiltonian cycle (note that fact 1 doesn't help us - $G$ has no leaf vertices). To do this:

  • Draw the graph with a blue pen, and label the degree of each vertex.
  • Assume, towards a contradiction, that $G$ has some Hamiltonian cycle $C$.
  • Apply fact 2 to each of the vertices of degree two. With a red pen, draw the edges that must be a part of $C$.
  • Use fact 3 to get the desired contradiction.
$\endgroup$
1
$\begingroup$

Illustration of graph G edges

The pic shows the graph G with the according vertices and edges.

Sorry I couldn't seem to add the desired red lines. I am making the assumption that the graph is a Hamiltonian ( I know it isn't) However, I manage to work out that vertices b, e and g have degrees of 2.

However, I don't understand how to use fact 3 to contradict this. Also I notice that D is a cut-vertex, can this be added to prove that the graph is not a Hamiltonian cycle.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.