Let $T=(V,E)$ be a tree with at least $3$ vertices. Assume that every vertex has either degree $1$ or a degree of at least $3$ (so there are no vertices with degree $2$). Prove that there are two end points in $T$ with a common neighbor.
My attempt:
Reason by contradiction, so assume that all end points have no common neighbor. Then there has to be at least one node in between every set of end points which is not a neighbor of both those end points. This node should have degree $\geq 2$. If this node has degree>$2$ the tree branches and we end up with new endpoints which will have a common neighbor. So the only way for the two endpoints to have no common neighbor is to let the node in between them have degree $2$. But this cannot be true by assumption. Hence, the two endpoints do have a common neighbor.
I am not satisfied with my own proof, and don't think it is completely satisfactory. Could anyone comment on my approach and point out improvements and/or show me a correct proof? Thanks in advance.
Best Answer
Suppose, toward a contradiction, that no two endpoints of $T$ have a common neighbor. Let $G$ be the graph obtained from $T$ by deleting each endpoint of $T$ along with it (unique) incident edge. Each vertex $v$ in $G$ originally had degree at least $3$ in $T$, and at most one of its incident edges was removed when we formed $G$ (because $v$ didn't have two leaves adjacent to it in $T$), so $v$ still has at least $2$ incident edges in $G$. Furthermore, $G$ isn't empty (because if all vertices of $T$ were endpoints then $T$ would have at most $2$ vertices, contrary to assumption). But then, being a nonempty graph in which every vertex has at least $2$ incident edges, $G$ would contain a cycle. That's also a cycle in $T$, contrary to the assumption that $T$ is a tree.