Graph Theory: Tree ($n\geq 4$ nodes) with no vertex degree $2$. Prove there is at least one vertex w/ 2 or 3 leaves as neigbors

Question

T: Trees with no vertex of degree 2 have more leaves than internal nodes

So far I have (proof by contradiction).

Consider the opposite. That all nodes have only 1 leaf as a neighbor. Take some vertex, $v_i $. It must be connected to 2 other vertices which must be internal nodes (deg(3)). However this would mean there could exist a tree with more internal nodes (2) than leaves which would contradict T. Hence the original claim is false. Hence there is at least one vertex with 2 or 3 leaves.

Feel like this isn't as watertight as I would like.

Answer 1

I assume you're asking for help with proving such things, and for improving the proof you wrote, and that you're NOT asking for a proof of this particular statement.

As a general hint, when you want to ask a question, it's a good idea to make the question very explicit. A "question mark" can be a big help.

Anyhow, assuming that's what you're looking for:

It might help to write that as a two-column proof, with a reason for every claim. For instance, the opposite of "trees with no vertex of degree 2 have more leaves that internal nodes" is not "all nodes have only one leaf as neighbor". You generally need to be very specific about your contradiction hypothesis, since setting up a false contradiction is one of the great non-proof techniques. (e.g., I'll prove to you that "all men are tall"; well, let's suppose that all men are short. Then ...)

Answer 2

One possible proof by contradiction (welcome comments)

Assume each node has max. 1 neighbor with is a leaf.

--> Every inner node has at least 2 neighbors which are inner nodes.

So now choose some inner node v. Visit a neighboring inner node v', then another v'' != v, etc..

After a finite number of steps we end up at an inner node already visited {I believe this is because there is always a way in and out of a node given min. 2 in-degree to any inner node}, i.e. there is a cycle.

This contradicts the original assumption that we have a Tree (no cycles). --> Hence each node must have 2 or 3 neighbors which are leaves.