Let T be a tree with n vertices,where n greater than or equal to 3.Show that there is a vertex V in T with d(V) greater than or equal to 2 such that every vertex adjacent to V ,except possibly for one ,has degree 1.
1
-
$\begingroup$ Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be put on hold. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$– José Carlos SantosCommented Dec 2, 2018 at 10:36
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let $T’$ be a subgraph of $T$ induced by the set of all vertices of $T$ which have degree at least $2$. Since $T$ is connected and $n\ge 3$, $T’$ is non-empty. Since $T’$ is a subgraph of a tree, it is forest, that is a union of mutually disjoint trees. Choose any of these trees and pick as the required vertex $v$ any its leaf, that is a vertex of degree $1$.
answered Dec 3, 2018 at 3:35