01 Key Concepts
Vertices and Edges
A graph consists of vertices (nodes/points) and edges (connections between pairs of vertices).
Degree of a Vertex
The number of edges connected to that vertex.
Directed vs. Undirected Graphs
In a directed graph, edges have a direction (one-way); in an undirected graph, edges go both ways equally.
Path 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.
Connected Graph
A graph where there is a path between every pair of vertices.
Weighted Graph
A graph where each edge has an associated numeric value (weight), often representing cost, distance, or time.
02 Key Formulas
- Sum of all vertex degrees = 2 * (number of edges)
03 Solved Examples
Example 1 A graph has vertices A, B, C, D with edges A-B, B-C, C-D, D-A. Find the degree of vertex B.
- Count the edges touching B: A-B and B-C.
- That's 2 edges.
Answer: Degree of B = 2
Example 2 A graph has 5 edges. Find the sum of all vertex degrees.
- Use the handshake formula: sum of degrees = 2 * number of edges = 2*5.
Answer: Sum of degrees = 10
Example 3 Is the graph with edges A-B, B-C, C-A a cycle?
- Check if it starts and ends at the same vertex, following distinct edges: A to B to C, then back to A.
- This forms a closed loop through 3 distinct vertices.
Answer: Yes, this is a cycle (a triangle)
04 Practice Questions
1A graph has edges A-B, B-C, A-C. Find the degree of vertex A.
2
2A graph has 4 edges. Find the sum of vertex degrees.
8
3What is the difference between a directed and undirected graph?
Directed graph edges have direction; undirected edges connect both ways equally
4What is a 'connected graph'?
A graph where a path exists between every pair of vertices
5What does a 'weighted graph' represent?
A graph where edges carry a numeric value, like distance or cost
📄 Graph Theory — Downloadable Worksheet
10 questions with a full answer key. Grab the PDF to print, or try the interactive version in your browser.