Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G$ be a graph where every vertex has degree 1 or 3. Let $X$ be the set of all vertices of degree 1. Suppose there exists a set of edges $Y$ such that by removing these edges from $G$, each component of the remaining graph is a tree which contains exactly one vertex in $X$. Determine $|Y|$ in terms of $|V(G)|$.

I really can't think of how to do this problem. Surely there are graphs that fulfill the requirements and both have the same $|V(G)|$ but different $|Y|$s? How can $|Y|$ be written solely in terms of $|V(G)|$?

share|cite|improve this question
up vote 6 down vote accepted

Suppose that G is split into $|X|$ trees with $n_1, n_2, \dots, n_{|X|}$ vertices respectively. Then we have that $n_1 + n_2 + \dots n_{|X|} = |V(G)|$. Furthermore, each component contains exactly one vertex from $X$. The total number of edges in the trees is $(n_1 - 1) + (n_2 - 1) + \dots + (n_{|X|} - 1) = |V(G)| - |X|$.

But the total number of edges in $G$ originally was $\frac{1}{2} \sum_v \text{deg}(v) = \frac{1}{2} (|X| + 3(|V(G)| - |X|)) = \frac{3}{2} |V(G)| - |X|$

Therefore, we've removed exactly $\frac{|V(G)|}{2}$ edges.

share|cite|improve this answer

Your Answer


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.