1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 ...)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.