Problema de la teoría de gráfico extraño

Question

Deje $G$ ser un gráfico donde cada vértice tiene grado 1 o 3. Deje $X$ ser el conjunto de todos los vértices de grado 1. Supongamos que existe un conjunto de aristas $Y$ de manera tal que mediante la eliminación de estos bordes de $G$, cada uno de los componentes de los restantes grafo es un árbol que contiene exactamente un vértice en $X$. Determinar el $|Y|$ en términos de $|V(G)|$.

Yo realmente no puedo pensar en cómo hacer este problema. Seguramente hay gráficos que cumplen con los requisitos, y ambos tienen el mismo $|V(G)|$, pero diferentes, $|Y|$s? ¿Cómo puede el $|Y|$ ser escritas exclusivamente en términos de $|V(G)|$?

Answer 1

Supongamos que G es dividida en árboles $|X|$ $n_1, n_2, \dots, n_{|X|}$ vértices respectivamente. Entonces tenemos que $n_1 + n_2 + \dots n_{|X|} = |V(G)|$. Además, cada componente contiene exactamente un vértice de $X$. El número total de los bordes de los árboles es $(n_1 - 1) + (n_2 - 1) + \dots + (n_{|X|} - 1) = |V(G)| - |X|$.

Pero originalmente fue el número total de aristas en $G$ $\frac{1}{2} \sum_v \text{deg}(v) = \frac{1}{2} (|X| + 3(|V(G)| - |X|)) = \frac{3}{2} |V(G)| - |X|$

Por lo tanto, hemos eliminado exactamente los bordes de $\frac{|V(G)|}{2}$.