Some exercises on Trees

A graph with no cycle is 0 cycle. So tree is a bipartite graph. Any path is a tree, but a tree is a path if and only if it has maximum degree 2.

Hint: A maximal non-trivial path in acyclic graph has 2 endpoints (this is also a connected spanning subgraph of G)

Prove this theorem:

Hint: Show A=>B (this implies C), B=>C (this implies A), C=>(A and B), (A=>D) and D=>A

You may choose any other combination of statements to prove equivalence as well.

1.A simple graph is connected if and only if it has a spanning tree. If G has unique spanning tree then G is a tree

​

2. Let T be a tree. Prove that the vertices of T all have odd degree if and only if for all

e ∈ E(T ), both components of T − e have odd order.

​

3. In a simple graph with diam(G)>=3 implies diam(G’)<=3

4. Prove that a tree with maximum degree ∆ > 1 has at least ∆ vertices of degree 1.

5. Find n(T) in terms of average degree “a”

​

​