2
$\begingroup$

Prove that if $G$ is a graph with degree of every vertex at most $3$, then it can be decomposed for graphs $C,T$, where $C$ is a sum of vertex-disjoint cycles and $T$ is a sum of trees.

I completely don't know how to approach. Whenever I want to solve some problem of graph theory I don't know how to start.

2 Answers 2

1

There is a natural iterative approach.

Until $G$ contains no cycle, do the following:

  1. Select a cycle $\gamma$ in $G$.
  2. Add $\gamma$ to $C$, and remove it from $G$. Here, by adding and removing I mean adding and removing edges - the formulation suggests that you want to decompose edges of $G$ (rather than vertices).

Once there are no cycles in $G$, it has to be a sum of trees. (It is well known that a connected acyclic graph is a tree, and accordingly a not-necessarily-connected acyclic graph is a sum of trees). Thus, you can denote whatever remains of $G$ by $T$ and you are done.

From the construction it is clear that $C$ is a sum of cycles, and we have shown that $T$ is a sum of trees. One thing that remains to be seen is that the cycles in $C$ are vertex-disjoint. Suppose otherwise, i.e. there are two cycles $\gamma$ and $\gamma'$ in $C$ that have a common vertex $v$. For the sake of concreteness, assume $\gamma$ was added to $C$ before $\gamma'$. At first, $v$ had at most $3$ entering edges. Since we deleted two edges entering $v$ when $\gamma$ was added to $C$, after that step $v$ had at most $3-2 = 1$ entering edge. Thus, it can't lie on any cycle after that step, since belonging to a cycle requires degree at least $2$.

2

Same idea without stepwise constructon of $C$: Among all subgraphs that are the sum of vertex-disjoint cycles, consider one with maximal number of edges in total and call it $C$. Let $T$ be the subgraph made up by the remaining edges. If $T$ contain a cycle $\gamma$ then it is not vertex-disjoint to $C$ by maximality, hence has a vertex $v$ in common with some cycle $\gamma'$ of $C$. Then $v$ is incident with (at least) two edges belonging to $\gamma$ and two belongiung to $\gamma'$ contradicting the degree condition. Hence $T$ is a forest.

  • 0
    A nice insight! I'd say your approach is more mathematical, while mine is more algorithmic.2012-09-08