0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
1
$\begingroup$

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$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the prompt response. However, I still didn't get the idea. Can you please elaborate further? Sorry, I have a hard time understanding graphs really. $\endgroup$ – Philip Benj Dec 1 '14 at 17:37
  • $\begingroup$ @PhilipBenjMarcobyEragon Have you tried to draw it? $\endgroup$ – dtldarek Dec 1 '14 at 17:43

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.