Discrete Mathematics: An Open Introduction, fourth edition
Oscar Levin · Open textbook
Read fourth-edition §§2.1–2.2 for graph definitions and trees. Reproduce the leaf argument.
Open the sourceGraphs: connection and redundancy
One extra edge can change a path into a cycle.
Prerequisites: 03 · Sets: the grammar of selection, 05 · From seeing a pattern to proving it, 12 · Counting without listing everything
Understand
Objectives
- Identify components, counting isolated vertices.
- Calculate graph rank as vertices minus components.
- Explain why a joining edge and a cycle edge have different rank effects.
Start with something you can see
Start the four-vertex graph lab with edges 1–2 and 2–3. Vertex 4 is isolated, so the component labels are {1,2,3} and {4}. Predict what happens when you add 3–4, then 4–1: the first joins components, while the second closes an existing path. Moving a vertex on the screen changes neither endpoint nor component. The MIT tree passage begins at 17:10. [1]
Give the idea a precise name
A graph has a vertex set V and an edge set E. A path joins vertices through edges; a cycle returns without repeating another vertex. An acyclic edge set is a forest; a connected forest is a tree. A spanning forest of a graph retains all vertices and one tree in each original component, including isolated vertices. The graphic matroid has edges as ground-set elements, and its independent sets are the forests.
r(E)=|V|−c(G); |F|=|V|−c(V,F) for a forest F
The symbol c(G) counts connected components of the full graph G=(V,E). For the second equality, (V,F) has every vertex but only selected forest edges F. A tree on m vertices has m−1 edges: remove a leaf and its single edge, then repeat until one vertex remains. Sum that count over all components. This proves the forest edge formula, and a spanning forest has r(E) edges.
Work one small world
With V={1,2,3,4}, add edges in this order. The table names components rather than relying on their positions or colors. The MIT leaf proof begins at 22:59. [2]
| Edges | Components | c | Rank |
|---|---|---|---|
| 1–2, 2–3 | {1,2,3}, {4} | 2 | 2 |
| add 3–4 | {1,2,3,4} | 1 | 3 |
| add 4–1 | {1,2,3,4} | 1 | 3 |
The final four edges form a cycle; delete any one and the remaining three are a spanning tree. For a four-cycle with an additional isolated vertex, c=2, rank 5−2=3, and the four perimeter edges yield four spanning forests, each retaining the isolated vertex.
Counterexample to “an added edge always raises rank”: after the path 1–2–3–4 exists, adding 4–1 does not merge components. It raises the edge count from three to four but leaves rank at three. The old path and the new edge form a cycle.
THE BRIDGEA signed incidence matrix will encode the same independent edge selections as column independence.
WHERE THIS IDEA STOPSThe formula |V|−c is graphic rank; do not count vertices as matroid ground-set elements.
Experiment
Use the Path preset in the graph lab, then the 4-cycle preset. Predict the component count, rank and bases before revealing the displayed values.
Does the new edge connect previously separate pieces, or merely add another route?
Check & explain
A four-cycle and one isolated vertex have how many edges in each spanning forest?
What happens when 4–1 is added to the path 1–2–3–4?
- It joins two components
- It creates a cycle without raising rank
- It removes a vertex
Teach back
For a square plus one isolated vertex, list all spanning forests and explain why none connects the isolated vertex without a new edge.
- Count isolated vertices as components.
- List the four ways to omit one perimeter edge.
- Say that the matroid ground set consists of edges.
Read deeper
Lec 8 | MIT 6.042J Mathematics for Computer Science, Fall 2010
MIT OpenCourseWare · Lecture · 83 min
Start at 16:30. Watch 22:59–26:59 for the leaf proof, 16:30–31:30 for its context, or the full 83-minute lecture.
Open the source