Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
A nice insight! I'd say your approach is more mathematical, while mine is more algorithmic. –  Feanor Sep 8 '12 at 13:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.