Prove that if $G$ is a graph with maximum vertex degree equal 3, then G can be divided into 2 edge-disjoint subgraphs $C$ and $F$, where $C$ is sum of vertex-disjoint simple cycles and $F$ is a forest.
2026-04-24 07:05:29.1777014329
Prove that if $G$ is a graph with maximum vertex degree equal 3, then G can be divided into 2 edge-disjoint subgraphs $C$ and $F$
92 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Consider cycles. Suppose there are two cycles sharing a vertex. Then you have one vertex with a degree of at least $4$, as each vertex in a cycle has degree $3$. And so any connected cycles must have an edge between them. That gives you the set $C$ pretty easily.
Now just take the edges not on a cycle. There is your forest. Note that $C$ and $F$ don't have to be vertex disjoint.