Graph Theory Basics
Graph theory studies networks of connected points. It has real-world applications in mapping, social networks, transport systems, and computer science.
What You Need to Know
Key Concept Diagram
A graph consists of vertices (nodes) and edges (connections) between them
A path visits each vertex at most once; a circuit returns to its start vertex
Euler paths traverse every edge exactly once; Euler circuits do the same and return to start
A connected graph has a path between every pair of vertices
Key Vocabulary
Vertex
A point or node in a graph (plural: vertices)
Edge
A connection or line between two vertices in a graph
Degree
The number of edges connected to a vertex
Euler path
A path that travels along every edge of a graph 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 and 7 edges. What is the sum of all vertex degrees?
Question 2
For an Euler circuit to exist, every vertex must have:
Question 3
Which real-world problem can graph theory help solve?
Key Concepts Summary
- ●A graph consists of vertices (nodes) and edges (connections) between them
- ●A path visits each vertex at most once; a circuit returns to its start vertex
- ●Euler paths traverse every edge exactly once; Euler circuits do the same and return to start
- ●A connected graph has a path between every pair of vertices