G − x and G − y are trees. Prove that deg(x) = deg(y). Let G be a graph. Assume G contains two vertices $x, y$ such that $G − x$ and
$G − y$ are trees. Prove that $\deg(x) = \deg(y)$.
I really don't know how to start with this problem, should we consider $G − \{x, y\}$ first?
 A: Since both trees are on $n-1$ vertices; counting in both ways the sum of degrees in $G$, we have the following:$$d(x)+2(n-2) = d(y)+2(n-2)$$ Hence your result.
A: Hint: Mostly play around with the Handshaking Lemma: That $\sum_{v\in V(H)}\deg_H(v)=2|E(H)|$, where $\deg_H(v)$ means the degree in graph $H$. Also, notice that $$\sum_{v\in V(G-x)}\deg_{G-x}(v)=\sum_{v\in V(G)}\deg_G(v)-2\deg_G(x).$$
A: Suppose $G$ is a graph of order $n$ and let $x,y\in G$ be such that both $G-x$ and $G-y$ are trees. This implies that $G-x-y$ is a forest with $k$ components. So that means $\deg_{G-y}(x)=\deg_{G-x}(y)=k.$
If $x$ and $y$ are adjacent in $G$ then $\deg_G(x)=\deg_G(y)=k+1$. If $x$ and $y$ are not adjacent in $G$ then $\deg_G(x)=\deg_G(y)=k.$
In either case, $\deg_G(x)=\deg_G(y).$
A: You have a good hunch, starting with $G - \{x,y\}$ is a good idea.
Hint:


*

*Let $k$ be the number of connected components of $G - \{x,y\}$.

*Observe that $G - \{x\}$ has exactly one connected component.

*Observe that $y$ connects each connected component of $G - \{x,y\}$ with at most one edge, otherwise $G - \{x\}$ would not be a tree.

*Same for $G - \{y\}$.


I hope this helps $\ddot\smile$
