[Math] About the proof of a graph is not Hamiltonian.

graph theoryhamiltonian-path

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?

Best Answer

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

Related Solutions

Graph Theory – Showing that No Hamilton Circuit Exists

Suppose that $v$ is a vertex of degree $2$. If $G$ has a Hamilton circuit, that circuit must pass through $v$, so it must include both of the edges incident at $v$. In particular, if the configuration

              o----o----o  
              u    v    w

occurs anywhere in $G$, it must be part of any Hamilton circuit in $G$. Such a circuit must be a circuit, so it must include some other path from $u$ to $w$ as well. This can be useful in proving that a graph does not have a Hamilton circuit: if there is no other path between $u$ and $w$ in $G$, then $G$ cannot have a Hamilton circuit.

[Math] Does this graph have Hamiltonian path and/or Eulerian paths

Recall that an Eulerian path exists iff there are exactly zero or two odd vertices. Since $v_0$, $v_2$, $v_4$, and $v_5$ have odd degree, there is no Eulerian path in the first graph.

It is clear from inspection that the first graph admits a Hamiltonian path but no Hamiltonian cycle (since $\operatorname{deg}v_0=1$).

The other two graphs posted each have exactly two odd vertices, and so admit an Eulerian path but not an Eulerian circuit.

Best Answer

Related Solutions

Graph Theory – Showing that No Hamilton Circuit Exists

[Math] Does this graph have Hamiltonian path and/or Eulerian paths

Related Question