Grades 9–12Discrete MathematicsLesson available
Graphs
Graphs as vertices and edges, degree and the handshake lemma, paths and connectivity, Euler circuits, trees and graph isomorphism.
math.discrete.graph-basics
Builds on
Required prerequisites, all the way down: 11
You will learn to
- Prove the handshake lemma and Euler's criterion for Eulerian circuits.
- Prove that a tree with n vertices has n − 1 edges.
- Decide whether two small graphs are isomorphic.
Definition
- A simple graph consists of a set V of vertices and a set E of two-element subsets of V, called edges.
- A tree is a connected graph with no cycles.
- Graphs G and H are isomorphic if there is a bijection between their vertex sets that preserves adjacency in both directions.
Theorem
- Handshake lemma: the sum of the degrees of all vertices is 2|E|.
- A connected graph has an Eulerian circuit if and only if every vertex has even degree.
- A tree on n vertices has exactly n − 1 edges, and any two of its vertices are joined by a unique path.
Common misconceptions
- Thinking a particular drawing determines the graph; very different drawings can show the same graph.
- Confusing Euler circuits (using each edge once) with Hamiltonian cycles (visiting each vertex once).
Leads to
Optional discoveries
- Structure-preserving maps: homomorphisms and isomorphisms A graph isomorphism is a structure-preserving bijection whose inverse also preserves structure.
- Quivers and path algebras Directed graphs (quivers) give rise to path algebras, whose modules are the representations of the quiver.
Learning pathways
Further reading
- J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (1976)