n this page, let us prove a graph is a tree if and only if it is minimally connected. Before proving this, let us recall the definition of a tree.

Definition of a Tree in Graph Theory

A connected graph without any circuit is called a tree.

Tree is Minimally Connected Proof

Theorem: Show that a graph G is minimally connected if and only if it is a tree.

Proof:

Let the graph G be minimally connected. So the removal of one edge make it disconnected. Therefore, there is no circuit. Hence, G is a tree.

Conversely, assume that G is a tree. So there exists a unique path between each pair of vertices. Hence, removal of one edge from the path makes the graph disconnected. So the graph G is minimally connected.

This completes the proof of the theorem.

Also Study:

1. Degree of a Vertex in Graph: Definition, Examples, Handshaking Theorem
2. Simple Graph has Two Vertices of Same Degree: proof
3. Prove that a tree with n vertices has (n-1) edges
4. Simple Graph with n Vertices and k Components have at most (n-k)(n-k+1)/2 Edges
5. Chromatic number of a complete graph with n vertices is n: Proof
6. Chromatic number of a cycle with n vertices is 2 if n even and 3 if n odd