BitWithBite
Discrete Mathematics · Quick Reference
Graph Theory Cheat Sheet
In one line: graph theory studies networks of connected points — used to model everything from social networks and road maps to computer networks and scheduling problems.
Key Ideas
1Vertices and Edges. A graph consists of vertices (nodes/points) and edges (connections between pairs of vertices).
2Degree of a Vertex. The number of edges connected to that vertex.
3Directed vs. Undirected Graphs. In a directed graph, edges have a direction (one-way); in an undirected graph, edges go both ways equally.
4Path and Cycle. A path is a sequence of edges connecting a sequence of distinct vertices. A cycle is a path that starts and ends at the same vertex.
5Connected Graph. A graph where there is a path between every pair of vertices.
Worked Examples
A graph has vertices A, B, C, D with edges A-B, B-C, C-D, D-A. Find the degree of vertex B.
Degree of B = 2
A graph has 5 edges. Find the sum of all vertex degrees.
Sum of degrees = 10
Is the graph with edges A-B, B-C, C-A a cycle?
Yes, this is a cycle (a triangle)
Formulas
Sum of all vertex degrees = 2 * (number of edges)
Practice Yourself
A graph has edges A-B, B-C, A-C. Find the degree of vertex A.
2
A graph has 4 edges. Find the sum of vertex degrees.
8
What is the difference between a directed and undirected graph?
Directed graph edges have direction; undirected edges connect both ways equally