Grades 9–12Discrete MathematicsPlanned
Graphs
Graphs as vertices and edges, degree and the handshake lemma, paths and connectivity, Euler circuits, trees and graph isomorphism.
math.discrete.graph-basics
The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.
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)