Discrete Mathematics - Trees

Question

Question: Prove that if a tree has a node of degree $n$, it has at least $n$ nodes of degree $1$.

My answer: From each of $n$ edges adjacent to the node of degree $n$ a path starts. Each of these paths eventually ends in a leaf. Since the tree has no cycles, then all these leaves are different, hence the tree has at least $n$ leaves, and degree of a leaf is $1$, thus, the tree has at least $n$ nodes of degree $1$.

I'm not sure about the strength of this argument. Can anybody give me some idea about my answer please.

Answer 1

Let v be a node with degree n in a finite graph.
Let v(k) be the k-th vertex for which v,v(k) is an edge.
Let p(k) be a path of maximal length from v through v(k).
As the path has no loops and is finite it will end in a leaf.

Now prove there are at least n leaves.

Answer 2

Suppose the tree has $k$ vertices.Then it has $k-1$ edges.

Assume on the contrary that there are at most $n-1$ leaves. Then the number of edges is at least: $$\frac{n+(n-1)+2(k-n)}{2}=\frac{2k-1}{2} > k-1$$ Contradiction.

Answer 3

This is a seed of an argument. You're right to think that it is unclear whether it will "grow up" into a healthy proof. Your readers will too. Here is how you can make your case more formally.

Let $T$ be the tree. We may choose $u$ be a vertex of $T$ with a degree of $n$. Let $\{u_1,u_2,...,u_n\}$ be the neighbors of $u$. For each $i\in1..n$, we may choose $P_i$ to be a path of maximal length in $T-u$ with origin $u_i$. For each $P_i$, Let $v_i$ represent the terminus of each $P_i$. (To be clear, if some $u_i$ is a leaf, then $P_i$ is a path of length $0$ with terminus $v_i=u_i$.)

From here, to formally complete the proof you must show that each $v_i$ is a leaf and that $v_i$ and $v_j$ must be different vertices when $i\ne j$. The former follows since the chosen paths are of maximal length, and the latter because $T$ is a tree. But each of these facts should get a whole sentence or three of their own.