EdTech

3 · Trees · Data Structures

Trees

·

What Is a Tree?

A tree is a connected graph with no cycles. In other words, every vertex belongs to one connected structure, and it is impossible to start at a vertex, follow edges, and return to that same vertex through a cycle.

An equivalent characterization uses paths: a graph is a tree exactly when every pair of vertices has one unique connecting path.

For example, consider vertices (A, B, C, D) with edges (AB), (AC), and (CD). The graph is connected, has no cycle, and has exactly one path between each pair of vertices. Therefore, it is a tree.

Equivalent Tests for a Tree

For a graph with (n) vertices and (m) edges, the following are equivalent ways to recognize a tree:

Test Condition
Connectivity and edge count The graph is connected and (m=n-1).
Acyclicity and edge count The graph has no cycles and (m=n-1).
Unique paths Every pair of vertices has exactly one connecting path.
Cut-edge test The graph is connected and every edge is a cut-edge.

A cut-edge is an edge whose removal disconnects a connected graph. In a tree, removing any edge disconnects the graph.

Six-vertex example

Suppose a graph has (6) vertices and (5) edges.

Forests and Spanning Trees

A forest is an acyclic graph. Each connected component of a forest is a tree. Thus, a single tree is a connected forest, while a forest may contain several separate trees.

For example, if one component contains (A-B-C) and another contains (D-E), the full graph has no cycles but is disconnected. It is a forest with two tree components, not one tree.

Every connected graph contains a spanning tree. One can be obtained by repeatedly removing an edge from a cycle until no cycles remain.

Cycle-removal example

Consider a connected graph with edges (AB), (BC), (CA), and (CD). The edges (AB), (BC), and (CA) form a cycle.

Remove (CA). The graph remains connected through (A-B-C), and the remaining edges (AB), (BC), and (CD) form a spanning tree on (A, B, C, D).

A Useful Property of Trees

Every tree with at least two vertices has at least two vertices of degree (1).

For the path

[ A - B - C - D ]

vertices (A) and (D) each have degree (1), while (B) and (C) each have degree (2). This example illustrates the required degree-(1) vertices.

Checking Tree Properties in Code

A practical tree check can combine connectivity, edge count, and cycle detection.

isTree(graph):
    n = number of vertices in graph
    m = number of edges in graph

    if n == 0:
        return false

    if m != n - 1:
        return false

    start a traversal from any vertex
    record every visited vertex
    detect whether a cycle is encountered during traversal

    if a cycle is found:
        return false

    if not all vertices were visited:
        return false

    return true

The edge-count condition checks whether (m=n-1). The traversal checks that the graph is connected and contains no cycle. A graph satisfying these tree conditions is a tree.

Common mistakes

Practice

  1. A graph has (8) vertices, (7) edges, and is connected. Is it a tree? State the test you used.
  2. A graph has no cycles but consists of three connected components. Is it a tree or a forest? Explain.
  3. Explain how repeated cycle-edge removal can produce a spanning tree of a connected graph.
  4. A tree has at least two vertices. What can you conclude about the number of degree-(1) vertices?

Key takeaways

Sources

  1. https://archive.nptel.ac.in/content/storage2/courses/111106050/Module3.pdf — archive.nptel.ac.in. Accessed 24 September 2026.
  2. https://archive.nptel.ac.in/content/storage2/courses/106104021/lecture13/13_5.htm — archive.nptel.ac.in. Accessed 24 September 2026.

Sources

  1. https://archive.nptel.ac.in/content/storage2/courses/111106050/Module3.pdf — archive.nptel.ac.in (Generated candidate citation)
  2. https://archive.nptel.ac.in/content/storage2/courses/106104021/lecture13/13_5.htm — archive.nptel.ac.in (Generated candidate citation)

Related topics