ECM 1415 Trees

Question 1

Theorem: a simple graph is connected if and only if it has a spanning tree

Answer 1

Proof of if:
Suppose that a simple graph G has a spanning tree T
- T contains every vertex of G
- Furthermore, there is a path in T between any two of its vertices
- Because T is a subgraph of G, there is a path in G between any two of its vertices
- Hence, G is connected

Proof of only if:
Now suppose that G is connected
- If G is not a tree, it must contain a simple circuit
- Remove an edge from one of these simple circuits
- The resulting subgraph has one fewer edge but still contains all the vertices of G and is connected.
- If this subgraph is not a tree, it has a simple circuit; so as before, remove an edge that is in a simple circuit.
- Repeat this process until no simple circuit remain
- The process terminates when no simple circuits remain
- A tree is produced because the graph stays connected as edges are removed
- This tree is a spanning tree because it contains every vertex of G