1. ## Graph Theory

Assumption 1 to the solution:

This can be prove as follows:
Direct Proof:
Let us consider the longest path {v0, v1},{v1, v2},...,{vn-1, vn} between two vertices x = v0 and y = vn in the tree (here the length of a path is how many edges it uses, and if there are multiple longest paths then we just pick one of them).
We claim that x and y must be leaves.
Suppose the contrary that x is not a leaf, so it has degree at least two (as we know that every node except root or leaf has at least degree 2).
This means x is adjacent to another vertex z different from v1. Observe that z cannot appear in the path from x to y that we are considering, for otherwise there would be a cycle in the tree. Therefore, we can add the edge {z, x} to our path to obtain a longer path in the tree, contradicting our earlier choice of the longest path. Thus, we conclude that x is a leaf.
By the same argument, we conclude y is also a leaf.
Thus we conclude that every tree with at least two vertices has at least two leaves.

Assumption 2 to the solution:

b)
If a tree has only 2 vertices.. then their degrees must be one...based on the definition on the tree...
so..we have 2 vertices with the degree two means..we have two leaves...
so...for every tree with at least two vertices has at least two leaves

Please could someone tell me which one is better and add details that may need specifying, thanks

(Part a my overall assumption)
-
A graph G is connected if for every pair of vertices u and v of G there is a path
from u to v. Otherwise G is disconnected.
-
A tree is a connected graph with no cycles.
-
A leaf is a vertex of degree 1.

2. ## Re: Graph Theory

Originally Posted by inayat

Assumption 1 to the solution:

This can be prove as follows:
Direct Proof:
Let us consider the longest path {v0, v1},{v1, v2},...,{vn-1, vn} between two vertices x = v0 and y = vn in the tree (here the length of a path is how many edges it uses, and if there are multiple longest paths then we just pick one of them).
We claim that x and y must be leaves.
Suppose the contrary that x is not a leaf, so it has degree at least two (as we know that every node except root or leaf has at least degree 2).
This means x is adjacent to another vertex z different from v1. Observe that z cannot appear in the path from x to y that we are considering, for otherwise there would be a cycle in the tree. Therefore, we can add the edge {z, x} to our path to obtain a longer path in the tree, contradicting our earlier choice of the longest path. Thus, we conclude that x is a leaf.
By the same argument, we conclude y is also a leaf.
Thus we conclude that every tree with at least two vertices has at least two leaves.

Assumption 2 to the solution:

b)
If a tree has only 2 vertices.. then their degrees must be one...based on the definition on the tree...
so..we have 2 vertices with the degree two means..we have two leaves...
so...for every tree with at least two vertices has at least two leaves

Please could someone tell me which one is better and add details that may need specifying, thanks

(Part a my overall assumption)
-
A graph G is connected if for every pair of vertices u and v of G there is a path
from u to v. Otherwise G is disconnected.
-
A tree is a connected graph with no cycles.
-
A leaf is a vertex of degree 1.
You need to define "longest path" because it is not obvious. Consider the following graph:

a----b----c----d

You want the longest path between b and c. Is that b,a,b,a,...,b,c where you jump back and forth between a and b a nigh infinite number of times? Because if that is the case, it is easy to show that a longest path does not exist between those two vertices. And it is easy to see that neither b nor c is a leaf.

I believe what you are looking for is to choose two vertices such that the shortest path between them is maximal. In other words, you cannot add any additional vertices to make the shortest path between them longer.

Your second attempt is not a proof at all.

4. ## Re: Graph Theory

Originally Posted by inayat

5. ## Re: Graph Theory

Originally Posted by SlipEternal
Thats the answer to part (b)

6. ## Re: Graph Theory

Originally Posted by inayat
Thats the answer to part (b)

7. ## Re: Graph Theory

Originally Posted by inayat

Please could someone tell me which one is better and add details that may need specifying, thanks[/FONT][/COLOR]
(Part a my overall assumption)
-
A graph G is connected if for every pair of vertices u and v of G there is a path
from u to v. Otherwise G is disconnected.
-
A tree is a connected graph with no cycles.
-
A leaf is a vertex of degree 1.
Suppose that $\mathcal{T}$ is a tree with at least two vertices: $v_1,v_2,\cdots,v_n$
Being a tree the graph has $n-1$ edges. By a theorem $\sum\limits_{k = 1}^n {\deg ({v_k})} = 2(n - 1) = 2n - 2$ .
How do we know that some vertex has degree $1~?$
From that where can you go?