1
$\begingroup$

I am trying to prove that if every node of a graph G has degree of at least 3 then G contains a cycle and a chord. My current approach is as follows:

  1. Separate the graph G into connected components and consider any component C.
  2. There exists a (hamiltonian) path that includes all the vertices in C. Label these vertices $V_0$...$V_k$.
  3. Consider $V_0$. In addition to being connected to $V_1$, it must also be connected with two other vertices on the path, $V_i$ and $V_j$, where $i < j$.
  4. We therefore have a cycle $\{V_0,V_1,V_2,...,V_i,...,V_j,V_0\}$. We also have a chord (a connection between two points within a cycle) between $V_i$ and $V_0$. Thus G contains both a cycle and a chord.

The part that I bolded and italicized is the part that's giving me trouble. I don't see how I can know that there is necessarily a path that connects all the vertices in C. And if such a path does not exist then I'm not sure how to get this proof to work.

EDIT

I thought of a possible solution but I want to confirm that it is valid:

  1. Separate the graph G into connected components and consider any component C.
  2. Consider a path of maximum length within C. Label these vertices $V_0$...$V_k$.
  3. We know that $V_0$ and $V_k$ cannot connect to vertices outside of the current path, because otherwise the current path would not be a maximal path. Thus $V_0$ and $V_k$ must only be connected to vertices along the path.
  4. Consider $V_0$. In addition to being connected to $V_1$, it must also be connected with two other vertices on the path, $V_i$ and $V_j$, where $i < j$.
  5. We therefore have a cycle $\{V_0,V_1,V_2,...,V_i,...,V_j,V_0\}$. We also have a chord (a connection between two points within a cycle) between $V_i$ and $V_0$. Thus G contains both a cycle and a chord.
$\endgroup$
  • $\begingroup$ It's simply not true that such a graph must have a Hamiltonian path. See Euler's Königsberg problem, for instance. $\endgroup$ – TonyK Nov 13 '13 at 8:50
  • $\begingroup$ @TonyK maybe I didn't get your example right, but if you mean the Konigsberg graph, then it definitely has a Hamiltonian path (even a Hamiltonian cycle). $\endgroup$ – DKal Nov 13 '13 at 9:01
  • $\begingroup$ @TonyK The Königsberg graph has no Eulerian path, but it does have a Hamiltonian path, in fact it has a Hamiltonian cycle. $\endgroup$ – bof Nov 13 '13 at 9:01
  • 1
    $\begingroup$ according to your edit it seems that it is enough for you to have a cycle with a chord in $G$ (not necessarily a cycle that contains ALL vertices in some connected component of $G$). $\endgroup$ – DKal Nov 13 '13 at 9:06
  • 2
    $\begingroup$ The proof in your edit is fine, so you don't need that false proposition about a Hamiltonian path. $\endgroup$ – bof Nov 13 '13 at 9:21
4
$\begingroup$

Here's an example of a connected $3$-regular graph with no Hamiltonian path. Let $H_1,H_2,H_3$ be three vertex-disjoint copies of $K_4$. For each $i\in\{1,2,3\}$ choose an edge $e_i$ of $H_i$ and subdivide it, making the midpoint of $e_i$ into a new vertex $x_i$. Finally, take a new vertex $y$ and add edges $x_1y,x_2y,x_3y$. This connected $3$-regular graph on $16$ vertices does not have a Hamiltonian path, because removing the vertex $y$ breaks it into three components.

$\endgroup$
  • $\begingroup$ Maybe check my answer below for a better illustration? $\endgroup$ – iBug Nov 11 '18 at 6:49
0
$\begingroup$

Here's a simple graph for you:

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