0
$\begingroup$

Given the following graph:

https://i.stack.imgur.com/fg2Q9.png

Is this graph Hamiltonian or not?

The answer is no. What I tried to prove is by using the fact that: "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." Following that we know, edges 11,6,4,12 must be in any circuit and the edges 17,18,19 and 9,15 must be in any circuit. Knowing that, what should I do to conclude that the graph is not Hamiltonian?

$\endgroup$
  • $\begingroup$ Look at the triangle $m,n,S$ $\endgroup$ – saulspatz Feb 8 at 20:27
  • $\begingroup$ @saulspatz That's a g, not an S. $\endgroup$ – Théophile Feb 8 at 20:31
  • $\begingroup$ @Théophile So it is. My annual eye exam isn't till next month. $\endgroup$ – saulspatz Feb 8 at 20:38
  • 1
    $\begingroup$ A Hamiltonian graph has to be biconnected (i.e., it must remain connected if you remove any vertex). Your graph contains a vertex whose removal disconnects the graph. $\endgroup$ – Rob Arthan Feb 8 at 20:40
1
$\begingroup$

The graph has drawn has a cut-vertex. Indeed removing $m$ breaks the graph into two components. If $G$ has a Hamiltonian circuit it cannot have any cut vertices [make sure you see why for yourself].

$\endgroup$
0
$\begingroup$

Edges $17$ and $19$ are incident on vertex $m$ and must be in any Hamiltonian circuit. But then vertex none of the other edges from vertex $m$ are in the circuit, therefore the circuit can't contain any edges connecting vertices $m, g, n$ to the rest of the graph.

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