Graph Theory
Graph theory studies networks of vertices connected by edges, with applications in mapping, logistics, social networks, and computer algorithms.
What You Need to Know
Key Concept Diagram
A graph consists of vertices (nodes) and edges (connections) between them
The degree of a vertex is the number of edges connected to it
A path visits each vertex at most once; a cycle returns to the starting vertex
An Eulerian path visits every edge exactly once; it exists when exactly 0 or 2 vertices have odd degree
A tree is a connected graph with no cycles, having exactly (n-1) edges for n vertices
Key Vocabulary
Vertex
A node or point in a graph; plural is vertices
Edge
A connection between two vertices in a graph
Degree
The number of edges connected to a vertex
Eulerian path
A path through a graph that visits every edge exactly once
Knowledge Check
Select the correct answer for each question. Click "Check Answer" to see if you are right.
Question 1
A graph has 5 vertices with degrees 2, 3, 4, 3, 2. What is the sum of all degrees?
Question 2
For an Eulerian path to exist in a graph, how many vertices may have odd degree?
Question 3
A tree with 8 vertices has exactly how many edges?
Key Concepts Summary
- ●A graph consists of vertices (nodes) and edges (connections) between them
- ●The degree of a vertex is the number of edges connected to it
- ●A path visits each vertex at most once; a cycle returns to the starting vertex
- ●An Eulerian path visits every edge exactly once; it exists when exactly 0 or 2 vertices have odd degree
- ●A tree is a connected graph with no cycles, having exactly (n-1) edges for n vertices