G - x y G - y son árboles. Demostrar que deg(x) = deg(y).

Question

Sea G un grafo. Supongamos que G contiene dos vértices $x, y$ tal que $G x$ y $G y$ son árboles. Demuestra que $\deg(x) = \deg(y)$ .

Realmente no sé cómo empezar con este problema, ¿deberíamos considerar $G \{x, y\}$ ¿primero?

Answer 1

Como ambos árboles están en $n-1$ vértices; contando de ambas formas la suma de grados en $G$ tenemos lo siguiente: $$d(x)+2(n-2) = d(y)+2(n-2)$$ De ahí su resultado.

Answer 2

Pista: Sobre todo jugar con el lema del apretón de manos: Que $\sum_{v\in V(H)}\deg_H(v)=2|E(H)|$ donde $\deg_H(v)$ significa el grado en el gráfico $H$ . Además, observe que $$\sum_{v\in V(G-x)}\deg_{G-x}(v)=\sum_{v\in V(G)}\deg_G(v)-2\deg_G(x).$$

Answer 3

Supongamos que $G$ es un gráfico de orden $n$ y que $x,y\in G$ sea tal que ambos $G-x$ y $G-y$ son árboles. Esto implica que $G-x-y$ es un bosque con $k$ componentes. Eso significa $\deg_{G-y}(x)=\deg_{G-x}(y)=k.$

Si $x$ y $y$ son adyacentes en $G$ entonces $\deg_G(x)=\deg_G(y)=k+1$ . Si $x$ y $y$ no son adyacentes en $G$ entonces $\deg_G(x)=\deg_G(y)=k.$

En cualquier caso, $\deg_G(x)=\deg_G(y).$

Answer 4

Tienes una buena corazonada, empezando por $G - \{x,y\}$ es una buena idea.

Pista:

• Sea $k$ sea el número de componentes conexas de $G - \{x,y\}$ .
• Observe que $G - \{x\}$ tiene exactamente una componente conexa.
• Observe que $y$ conecta cada componente conexo de $G - \{x,y\}$ con una arista como máximo, en caso contrario $G - \{x\}$ no sería un árbol.
• Lo mismo para $G - \{y\}$ .

Espero que esto ayude $\ddot\smile$