STEP-BY-STEP LESSON · §10.4
Trees: Examples and Basic Properties
Recognize a tree through connectedness and absence of cycles.
Before you begin
Connectedness
An undirected graph is connected when each pair of vertices can be joined by a path. Otherwise the maximal connected parts are its connected components. Isolated vertices form one-vertex components.
Cycles and repeated vertices
A simple circuit is a nonempty closed walk that returns to its start without repeating any other vertex or any edge. In a simple graph it uses at least three edges. Loops and parallel edges require the graph’s stated convention; a tree has no cycle.
Symbols
- |E|=|V|−1
- edge count of a finite tree
Definitions and notation for this topic
Tree
A nonempty connected undirected graph with no circuits. Equivalently, a connected simple undirected graph with no cycles.
A finite tree has |E|=|V|−1 and a unique path between every two vertices. Loops and parallel pairs would create circuits and are therefore excluded.
Separate glossary example
A—B—C is a tree.
Root and depth
depth(v)
A rooted tree has a designated root. The depth of v is the number of edges on the unique path from the root to v; the root has depth zero.
The parent is the preceding vertex on that root path; children are one level farther away. Depth counts edges, not vertices, and is not a vertex’s degree.
Separate glossary example
If r is the root and the path is r—a—v, then depth(a)=1 and depth(v)=2.
Spanning tree
A spanning tree of a connected undirected graph uses every vertex of G and a subset of its edges, while remaining connected and without circuits.
A finite spanning tree has |V|−1 edges. A minimum spanning tree minimizes total edge weight among spanning trees; it need not minimize the route from one fixed source to every vertex.
Separate glossary example
In a triangle with edges AB=2, BC=3, AC=7, selecting AB and BC gives a spanning tree of total weight 5.
Step by step
Step 1 / 6
Connect all vertices
A tree is a connected undirected graph without cycles. A collection of disconnected trees forms a forest.
Absence of cycles alone is insufficient without connectedness.
Worked example
A star has center O connected to A,B,C,D. Why is it a tree?
- Any two leaves are connected through O, so the graph is connected.
- A leaf has only one incident edge and cannot lie on a cycle. There are no cycles.
- There are 5 vertices and 4 edges, as n−1 requires.
Optional self-check
A forest with nine vertices has six edges. How many connected components does it have?
Show answer
Use edges=vertices−components: 6=9−c, hence c=3. Isolated vertices count as components.