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.

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|improve this question

1 Answer 1

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|improve this answer

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.