I'm not certain if the following statement is true: If G is a $2 \le k$-th regular graph then every edge is part of a circle. I was trying to prove this lemma for a bigger proof, I'd like to get a lead for this. Thanks in advanced.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ By a circle do you mean some cycle? An induced cycle? Or perhaps something more specific $\endgroup$– Uri George PeterzilCommented Jun 23 at 18:45
-
$\begingroup$ Also, I assume you mean a finite graph? $\endgroup$– Uri George PeterzilCommented Jun 23 at 18:46
-
$\begingroup$ @UriGeorgePeterzil finite graph, and a simple cycle. $\endgroup$– csmathstudent8Commented Jun 23 at 18:47
-
$\begingroup$ I unfortunately can only come up with a proof which is very much non-elementary and only works for even $n$, if you’re interested. It uses covering theory from algebraic topology. $\endgroup$– Uri George PeterzilCommented Jun 23 at 19:27
-
$\begingroup$ @UriGeorgePeterzil This is kind of material I'vent been taught, but toda anyways. $\endgroup$– csmathstudent8Commented Jun 24 at 10:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
An edge is a cut edge if and only if it is not part of any cycle. Therefore every edge is part of some cycle exactly when the graph has no cut edges: it is $2$-edge-connected.
This means that to look for counterexamples, we can go to https://houseofgraphs.org/ and search for graphs that (1) have edge connectivity only $1$, and (2) are regular. The smallest counterexample found is here.
All counterexamples are $k$-regular for odd $k$, though; the statement is true for even $k$. In fact, more is true: if every vertex in a graph $G$ has even degree (whether or not the degrees are all the same) then $G$ can be decomposed into edge-disjoint cycles (and therefore in particular every edge is part of some cycle). This has a quick proof by induction:
- it is trivially true if $G$ has no edges,
- and if $G$ does have edges, then any nontrivial connected component of $G$ has minimum degree $2$, so we can (greedily) find a cycle inside it and delete its edges. Now, we're left with a graph that has fewer edges, but within which all degrees are still even, so it can be decomposed into edge-disjoint cycles by the inductive hypothesis. Together with the cycle we deleted, we get a cycle decomposition of $G$.
answered Jun 24 at 2:47