Every nonhamiltonian 2-connected graph has a theta subgraph

Question

If a graph $G$ has a spanning cycle $Z$, then $G$ is called a Hamiltonian graph and $Z$ has a Hamiltonian cycle. A theta graph is a block with two nonadjacent vertices of degree 3 and all other points of degree 2.

Question: How am I going to show that every nonhamiltonian 2-connected graph has a theta subgraph?

Thanks in advance.

Answer 1

I'm assuming that $\theta$ graph is a union of three paths of length at least 2 with common end-points (i.e. each path has at least 3 vertices including the endpoints), that is, it looks like the $\theta$ symbol.

Hint:

• Let $Z$ be the longest simple cycle in the graph.
• If $|Z| < n$ then there exists a vertex $v \notin Z$, such that $v$ is adjacent to $Z$.
• Let $u \in Z$ be a neighbor of $v$ and let $u'$ be a successor of $u$ on $Z$. Then, there is no $(Z\setminus\{u'\})$-vertex-disjoint path from $v$ to $u'$ (in particular $v$ and $u'$ are not adjacent).

I hope this helps $\ddot\smile$