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)|$?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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