Tree characterizations

Theorem 1.1. The following conditions for a graph G are equivalent:

(1) G is a tree.

(2) G is connected and m = n − 1.

(3) G is acyclic and m = n − 1.

(4) G is connected and every edge is a bridge.

(5) In G any two given vertices are linked by a unique path.

Proof. The implications (1)⇒(2), (1)⇒(3), (1)⇒(4), (1)⇒(5), (3)⇒(1) result directly from the above propositions. Implication (4)⇒(1) is straightforward with lemma (An edge of a graph G is a bridge if and only if it does not belong to a cycle of G.) Implication (5)⇒(1) is easy:

if there was a cycle in G, one of its vertices would be joined to itself on the one hand by the cycle, considered as a (closed) path, and on the other hand by the path with of zero length that this vertex defines. This contradicts the hypothesis of the uniqueness of a path linking  any two vertices. To end the proof, that is to verify that these implications are sufficient, we must demonstrate implication (2)⇒(1). Consider  a graph G verifying (2). Remove, as long it is possible, an edge which is not a bridge (first in graph G, and then in the current graph obtained).

The spanning subgraph G^/ obtained is connected, like G, because each of the edges removed was not a bridge. It is also an acyclic graph since  it now has nothing but bridges and thus cannot have any cycle (An edge of a graph G is a bridge if and only if it does not belong to a cycle of G.).

This graph Gis therefore a tree, spanning a subgraph of G. Let m^/ be the number of edges of G^/.We have m^/= n−1= m. Thus, G^/having the same  number of edges as G, G^/= G and G is therefore a tree.

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(48-49)

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength