1
$\begingroup$

*Edit: $\delta$ is the minimal vertex degree in the graph

So I've noticed a number of threads here on how to show that a graph with $\delta \geq 2 $ contains a cycle but I can't find a way to prove the existence of two cycles and extending it to even cycles.

I've considered creating a subgraph $G' $ by removing edges of vertices with odd degree. Since $\delta \geq 4 $, we'd be left with vertices that would be even and with a degree $\geq 4 $. Assuming that $G $ is connected and each vertex degree is even, there must be an Eulerian cycle. Each vertex would be in the cycle at least twice because of $\delta $ so we'd be able to cut out the Eulerian cycle into a number of smaller cycles... but I'm not sure how to show that there will be even cycles.

Sorry for the inconsistent idea, I'm still new to proofs in Graph theory since the way of proving things here is very different from calculus or algebra.

$\endgroup$
2
  • 1
    $\begingroup$ Might be worth explaining what $\delta$ is, for those who do not have access to the textbook you are using. $\endgroup$ Commented Mar 31 at 15:56
  • 1
    $\begingroup$ @PrimeMover, thank you for the reminder. $\endgroup$ Commented Mar 31 at 16:00

1 Answer 1

1
$\begingroup$

Let $v_1, v_2, …, v_n$ be a maximal path in the graph. The degree of $v_1$ is at least $4$. Due to maximality of the path, all neighbours of $v_1$ belong to the path. Let them be $$v_2, v_i, v_j, v_k$$ in that order along the path.

enter image description here

Consider cycles $C_1, C_2, C_3$ from the picture. If two of them are even, then we’re done. If all are odd then the cycles $C_1\cup C_2$, $C_2\cup C_3$ are even. If only one of them is even (say $C_3$) then $C_2\cup C_3$ is also even.

By $C_i\cup C_j$ we denote the “embracing” cycle.

$\endgroup$
2
  • $\begingroup$ Thank you for this. Is there a way to show that there will be at least two cycles (even or odd, doesn't matter). Because you've immediately assumed that there must be those 3 cycles. Could we encounter a situation where we don't have 3 cycles to begin with? Or does it all come down to the minimal vertex degree being four? $\endgroup$ Commented Mar 31 at 17:02
  • 1
    $\begingroup$ Yes, since the degree of $v_1$ is $4$ and the path is maximal, the edges from $v_1$ go to the vertices of the path. Of course, cycles are created as shown in the picture. $C_1=(v_1v_2v_3…v_i)$, $C_2=(v_1v_iv_{i+1}v_{i+2}…v_j)$, $C_3=(v_1v_jv_{j+1}v_{j+2}…v_k)$. $\endgroup$
    – Aig
    Commented Mar 31 at 17:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .