maths.free › Discrete Math & Logic › Trees and spanning trees
Trees and spanning trees
Characterisations of trees, why a tree has n - 1 edges, rooted and binary trees, spanning trees and how to count them.
A tree is a connected graph with no cycles. Trees are the minimal connected graphs, and several conditions on a graph \( G \) with \( n \) vertices turn out to be equivalent: \( G \) is a tree; every two vertices are joined by exactly one path; \( G \) is connected and has \( n - 1 \) edges; \( G \) has no cycles and has \( n - 1 \) edges; \( G \) is connected, but removing any edge disconnects it. Any two of "connected", "acyclic" and "\( n - 1 \) edges" imply the third.
Why \( n - 1 \) edges? Every tree with at least two vertices has a leaf, a vertex of degree 1: follow a longest path, and its last vertex cannot have another neighbour (that would extend the path or close a cycle). Removing a leaf and its edge leaves a tree with one fewer vertex and one fewer edge, so induction on \( n \) gives \( |E| = n - 1 \). A forest (a graph with no cycles) with \( c \) components has \( n - c \) edges.
A rooted tree picks one vertex as the root, which gives every other vertex a parent, and a binary tree gives every vertex at most two children. A binary tree of height \( h \) has at most \( 2^{h+1} - 1 \) vertices, so a binary tree holding \( n \) items has height at least about \( \log_2 n \). That bound is why balanced search trees answer queries in logarithmic time, and why any sorting method that compares pairs needs about \( n \log_2 n \) comparisons in the worst case: its decision tree must have at least \( n! \) leaves, so its height is at least \( \log_2 n! \).
A spanning tree of a connected graph is a tree using all of its vertices and some of its edges; every connected graph has one (delete edges from cycles until none remain). The number of spanning trees is given by the matrix tree theorem: delete one row and the matching column of the Laplacian \( L = D - A \) (degrees on the diagonal, minus the adjacency matrix), and take the determinant. For \( K_4 \) the example gets 16, which agrees with Cayley's formula: \( K_n \) has \( n^{n-2} \) spanning trees.
Picture it: a tree is a skeleton that holds every vertex together with nothing spare: add any edge and you create exactly one cycle, remove any edge and it falls into two pieces.
Think it: "remove a leaf and use induction" is the standard proof pattern for trees, just as "remove the last element" is for sequences. When you need a cheapest network that connects every vertex, Kruskal's algorithm (add the cheapest edge that makes no cycle) and Prim's algorithm (grow one tree by its cheapest outgoing edge) both find a minimum spanning tree.
Worked example · det [[3,-1,-1],[-1,3,-1],[-1,-1,3]]
Det [[3,-1,-1],[-1,3,-1],[-1,-1,3]]
Step by step
- \det\left[\begin{matrix}3 & -1 & -1\\-1 & 3 & -1\\-1 & -1 & 3\end{matrix}\right]
Determinant of a 3×3 matrix.
- = + (3) \det\left[\begin{matrix}3 & -1\\-1 & 3\end{matrix}\right] - (-1) \det\left[\begin{matrix}-1 & -1\\-1 & 3\end{matrix}\right] + (-1) \det\left[\begin{matrix}-1 & 3\\-1 & -1\end{matrix}\right]
Cofactor (Laplace) expansion along the first row, with alternating signs + − +.
- = (24) + (-4) + (-4)
Each 2×2 minor is ad − bc.
- \det A = 16
Result.
Reveal the answer
Now you Pick a problem, or type or draw your own. Every step, a picture, the answer hidden until you ask.
Symbols used here
Tap any symbol for the full definition, a picture, and what every letter in it means.
How to: Trees and spanning trees
- Check that the graph is connected and count its edges.
- With n vertices, n - 1 edges and connectivity, it is a tree; with more edges it has a cycle.
- For proofs about trees, remove a leaf and apply induction on the number of vertices.
- To count spanning trees, build the Laplacian, delete one row and column, and take the determinant.
Questions people ask
Does every tree with at least two vertices have two leaves?
Yes. Both ends of a longest path are leaves. A path graph has exactly two, and a star has n - 1.
Is a minimum spanning tree unique?
It is when all edge weights are different. With equal weights there can be several, all with the same total weight.
What makes mathematics "discrete"?
It deals with separate, countable objects (integers, graphs, statements) rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.
How does a proof by induction work?
Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.
What order should I take these lessons in?
Logic and proof first, because every later lesson proves things. Then induction, sets, relations and functions, counting, recurrences, graphs, Boolean algebra and automata, and finally algorithms and complexity, which use nearly everything before them.
Is discrete mathematics the same as the maths of computer science?
Largely. Data structures are graphs and trees, correctness arguments are induction, running times are recurrences and sums, circuits are Boolean algebra, and what a computer can do efficiently is the subject of the last lessons. It is also ordinary mathematics in its own right.
Do I need calculus for this course?
No. School algebra is enough. A little familiarity with limits helps when comparing growth rates, and the lesson on asymptotic analysis explains the one limit fact it uses.
More in Discrete Math & Logic
Truth tablesSums and inductionProof by inductionAlgorithms and growth of functionsPredicate logic and quantifiersDirect proof, contrapositive and contradictionStrong induction and the well-ordering principleRelations: equivalence relations and partial ordersFunctions and cardinalityCounting: rules, choices and bijectionsThe pigeonhole principleSolving linear recurrence relationsGraphs: degrees, paths and connectivityEuler and Hamilton paths