Graph theory textbooks present a list of "equivalent conditions for a tree" – a battery of seemingly different properties lined up one after another. But they are all saying the same thing in different words. A tree is a connected graph with absolutely no redundancy, and the seven equivalent conditions are simply seven perspectives on that single idea.

1 Definition and intuition

Informally, a tree is "a connected graph on $n$ vertices using the bare minimum of $n-1$ edges."

This tree has 6 vertices and 5 edges. Remove any edge and the graph becomes disconnected; add any edge and a cycle appears.

2 Seven equivalent conditions – all saying the same thing

The following seven conditions on an $n$-vertex graph $G$ are mutually equivalent.

At first glance these appear to be seven distinct properties, but their essence is one. Let us weave them into a single narrative.

3 Zero redundancy – the soul of a tree

How many edges are needed, at minimum, to make $n$ vertices connected?

So $n-1$ is the minimum cost of connectivity. A tree is a graph that achieves this minimum exactly.

From here, the relationships among the conditions become transparent:

Condition 1 (connected + acyclic)$\iff$Condition 2 (connected +$n-1$edges): If a connected graph had $n$ or more edges, it would contain at least one "surplus" edge, and that surplus inevitably creates a cycle. Conversely, a connected graph with no cycle has exactly $n-1$ edges.

Condition 4 (exactly one path between every pair): If there were zero paths between some pair, the graph would not be connected. If there were two or more paths, their union would contain a cycle. "Exactly one" is another way of saying zero redundancy.

Condition 5 (every edge is a bridge): Because there is no redundancy, every single edge is load-bearing. Remove one and the structure collapses – there is no backup.

Condition 6 (every non-edge creates a cycle): Since there is already exactly one path between every pair of vertices, adding a new edge creates a second path, and the two paths together form a cycle.

4 The power of the edge-count formula

The simple formula $|E|=n-1$ is remarkably powerful.

5 Rooted trees – the protagonists of computer science

In computer science, "tree" almost always means rooted tree. File systems, the DOM, parse trees, binary search trees – all are rooted trees.

6 Spanning trees – the skeleton of a graph

A spanning tree is the "skeleton" of the original graph: it strips away all surplus edges, preserving only what is needed for connectivity.

This is intuitively clear. Starting from a connected graph, repeatedly remove an edge that lies in a cycle. Each such removal preserves connectivity. When no cycle remains, the result is a tree – a spanning tree.

7 Takeaway

The beauty of trees is captured in two words: zero redundancy. The seven equivalent conditions express this property from the perspectives of connectivity, acyclicity, edge count, path uniqueness, and the criticality of each edge. This "knife-edge structure" is deeply connected to the greedy algorithms we examine in the next article.