Combinatorics and Graph Theory Show that every edge in a tre

Combinatorics and Graph Theory

Show that every edge in a tree is a bridge, and that every nonleaf vertex is a cut vertex.

Solution

Note a fact : An edge of a graph G is a bridge if and only if it lies on no cycle of G. (This is famois bridge theorem, proof can be foud in any standard book , if you cant find then let me know).

Using this,

Since T contains no cycles, every edge e of T is not on a cycle of T, and so by the Bridge Theorem (Theorem 6), e is a bridge of T

Second fact also follows from definitions:

Non leaf vertex means vertex degree is greater than 1 , moreover our graph is a tree so vertex has no loops and there is a unique path between any 2 vertices so if we remove a non leaf vertex then obviously number of components will increase.