# Thread: graph theory problem

1. ## graph theory problem

This is my problem...

Let F be a forest with degree sequence (1,....1, 2, 3, 5, 7, 11, 13). Assuming that F has 3 components, what is the number of end vertices of F?

I've drawn a tree with 3 components and my picture has 41 vertices. There are 6 vertices that have degree > 1. I'm certain this is true but I think there might be a formula to prove this is true but my Wilson book isn't helping me very much. If anyone has any idea, let me know. Thank you.

2. ## Some graph suggestions

Here's 2 ways to construct a forest. Please tell me if these are legal:

(2-3), (5-7), (11-13).
(2-3-5), (7,11), (13).

So what do these look like? I've attached a picture of what (2-3) represents.
If these graphs match your criteria, I count 1 degree 1 vertex hanging off the "2" in the (2-3) graph, and 2 degree 1 vertices hanging off the "3". Continuing, I count 35 degree 1 vertices total. I get the same count in the second layout I suggested.

and I get 35 end vertices of degree 1 as well. and I drew two pics like what you get as well. But is a picture really justifying the answer? I'm trying to think of a proof or argument to add to show that's right.

4. ## start of a proof?

I applaud your desire to get a proof.

If all 6 of the degree > 1 vertices formed it's own component, there would be 41 degree 1 vertices. We have to get rid of 3 components by combining vertices. In the course of doing so, don't we lose 1 edge per 'degree > 1' vertex? So in the first forest, we lost 2 degree 1 vertices by forming the first component, and the same for the other two. Then 41 - 3*2 = 35.

5. ## hi

That's really interesting. I didn't consider what the condition would be if it was in one component. That makes sense to me.