Welcome to Graph Theory!
Welcome to Graph Theory, a core component of your AS 2 Section D: Discrete and Decision Mathematics module. At first glance, the word "graph" might make you think of \(x\)- and \(y\)-axes with curved lines or bar charts. In Decision Mathematics, however, a graph is something completely different and exciting!
Here, a graph is a visual network made of dots (called vertices) connected by lines (called edges). We use graphs to model real-world networks such as computer connections, road and rail systems, social media friendships, and delivery routes. Graph theory gives us the mathematical toolkit to understand how things are connected and to solve complex logistical problems efficiently.
Don't worry if this seems like a brand-new way of doing maths. The rules are logical, visual, and straightforward once you learn the key vocabulary.
1. Anatomy of a Graph: Core Definitions
Let us begin by establishing the fundamental building blocks of graph theory.
• Vertex (plural: Vertices) or Node: A point representing an object (for example, a town, a computer, or an intersection). We usually label vertices with capital letters such as \(A, B, C\).
• Edge (or Arc): A line segment or curve linking two vertices, representing a connection or relationship (such as a road between two towns). An edge connecting vertex \(A\) to vertex \(B\) is written as \(AB\) or \((A, B)\).
• Degree (or Valency) of a Vertex: The number of edges connected to that vertex. We denote the degree of a vertex \(v\) as \(\deg(v)\) or \(d(v)\).
• Loop: An edge that starts and finishes at the very same vertex. Crucial Rule: A loop adds 2 to the degree of that vertex because the edge leaves and returns to the same point.
• Multiple Edges: Two or more edges directly connecting the same pair of vertices (for instance, two distinct roads linking Town \(A\) and Town \(B\)).
• Simple Graph: A graph that contains no loops and no multiple edges. In AS Decision Mathematics, many problems focus on simple graphs.
Did You Know?
Graph theory was born in 1736 when the famous mathematician Leonhard Euler solved the puzzle of the Seven Bridges of Königsberg. The city wanted to know if a person could walk through the city crossing each of its seven bridges exactly once. Euler proved mathematically that it was impossible by inventing graph theory!
Key Takeaway
A graph is composed of vertices (points) and edges (lines). The degree of a vertex is the count of edge-ends touching it. Remember: a single loop counts as 2 towards that vertex's degree.
2. The Handshaking Lemma
One of the most important theorems in graph theory is the Handshaking Lemma. It gets its name from an everyday analogy: every time two people shake hands, two hands are involved in that single handshake.
The Formula
For any undirected graph with \(V\) vertices and \(E\) edges:
\(\sum \deg(v) = 2E\)
In plain words: The sum of the degrees of all vertices is equal to twice the number of edges.
Why is this always true?
Every single edge has exactly two ends. Therefore, drawing one edge increases the total sum of the degrees in the graph by 2.
Two Vital Consequences:
1. The sum of the degrees of all vertices in any graph is always an even number.
2. The number of vertices with an odd degree must always be even (e.g., a graph can have 0, 2, 4, or 6 odd-degree vertices, but never 1, 3, or 5).
Worked Example: Checking Graph Validity
Question: Can a graph exist with 5 vertices having degrees \(3, 3, 3, 2, 1\)?
Step 1: Find the sum of the degrees: \(3 + 3 + 3 + 2 + 1 = 12\).
Step 2: Count the number of odd-degree vertices: Vertices with degrees 3, 3, 3, and 1 give a total of 4 odd vertices.
Conclusion: The sum is even (12) and the number of odd vertices is even (4), so this graph can exist. The graph would have \(E = \frac{12}{2} = 6\) edges.
Common Mistake to Avoid
Exam Trap: If an exam question asks whether a graph with degrees \(2, 3, 4, 4, 4\) can exist, check the sum immediately: \(2 + 3 + 4 + 4 + 4 = 17\). Since 17 is odd (and there is only 1 odd vertex), such a graph is impossible!
Key Takeaway
Sum of degrees \(= 2 \times \text{number of edges}\). Total degree sum is always even, and the count of odd-degree vertices is always even.
3. Special Families of Graphs
You will frequently encounter specific categories of graphs in your exam. Let us review each one clearly.
A. Complete Graphs (\(K_n\))
A complete graph is a simple graph in which every single vertex is directly connected to every other vertex by an edge. A complete graph with \(n\) vertices is denoted by \(K_n\).
• In \(K_n\), each of the \(n\) vertices is connected to the remaining \((n - 1)\) vertices. Thus, every vertex has degree \(n - 1\).
• The total number of edges in \(K_n\) is given by the formula:
\(E = \frac{n(n - 1)}{2}\)
• Example: For \(K_5\), \(n = 5\). Every vertex has degree \(5 - 1 = 4\). The total number of edges is \(\frac{5 \times 4}{2} = 10\).
B. Bipartite Graphs & Complete Bipartite Graphs (\(K_{m,n}\))
A bipartite graph is a graph whose vertices can be divided into two distinct sets, \(X\) and \(Y\), such that every edge joins a vertex in set \(X\) to a vertex in set \(Y\). No edge ever connects two vertices in the same set.
Real-world Analogy: Think of set \(X\) as a set of workers and set \(Y\) as a set of jobs. An edge represents a worker qualified to do a specific job. Workers do not connect to workers, and jobs do not connect to jobs.
A complete bipartite graph, denoted \(K_{m,n}\), is a bipartite graph where every vertex in set \(X\) (containing \(m\) vertices) is connected to every vertex in set \(Y\) (containing \(n\) vertices).
• Total number of vertices \(= m + n\)
• Total number of edges \(= m \times n\)
• Vertices in set \(X\) each have degree \(n\); vertices in set \(Y\) each have degree \(m\).
C. Trees and Spanning Trees
A connected graph is one where there is a path between every pair of vertices (the graph is in one single piece).
• A tree is a connected graph that contains no cycles (no closed loops).
• For any tree with \(n\) vertices, the number of edges is always strictly:
\(E = n - 1\)
• A spanning tree of a connected graph \(G\) is a subgraph that includes all the vertices of \(G\) and is a tree.
D. Subgraphs and Directed Graphs (Digraphs)
• Subgraph: A graph whose vertices and edges are subsets of another graph.
• Directed Graph (Digraph): A graph where each edge has an assigned direction (shown by an arrow). Edges are often called directed arcs (e.g., representing one-way streets).
Key Takeaway
• \(K_n\) has \(n\) vertices and \(\frac{n(n-1)}{2}\) edges.
• \(K_{m,n}\) has \(m + n\) vertices and \(m \times n\) edges.
• A tree with \(n\) vertices has no cycles and exactly \(n - 1\) edges.
4. Routes Through Graphs: Walks, Trails, Paths, and Cycles
Examiners love testing the precise definitions of how we move through a graph. Let us clarify them step-by-step.
• Walk: A general sequence of edges and vertices joining a sequence of vertices. Vertices and edges can be repeated as many times as you like.
• Trail: A walk in which no edge is repeated. (Vertices may be visited more than once).
• Path: A trail in which no vertex is repeated (and therefore no edge is repeated either).
• Cycle: A closed path. It starts and ends at the same vertex, visiting other vertices without repeating any vertex along the way.
Quick Memory Aid
• Trail = No repeated Tracks (edges).
• Path = No repeated Points (vertices).
5. Eulerian and Hamiltonian Graphs
Two fundamental concepts in Graph Theory sound similar but focus on different elements: edges versus vertices.
A. Eulerian Graphs (Focus on EDGES)
An Eulerian trail is a trail that visits every single edge in the graph exactly once.
• Eulerian Graph: A connected graph that contains an Eulerian circuit (a closed trail visiting every edge once, starting and finishing at the same vertex).
Condition: A connected graph is Eulerian if and only if EVERY vertex has an EVEN degree.
• Semi-Eulerian Graph: A connected graph that contains an open Eulerian trail (visiting every edge once, but starting and finishing at different vertices).
Condition: A connected graph is semi-Eulerian if and only if it has EXACTLY TWO vertices of ODD degree. The trail must start at one odd vertex and end at the other odd vertex!
B. Hamiltonian Graphs (Focus on VERTICES)
A Hamiltonian cycle is a cycle that visits every single vertex in the graph exactly once (and returns to the start vertex).
• Hamiltonian Graph: A graph that contains a Hamiltonian cycle.
• Semi-Hamiltonian Graph: A graph that contains a Hamiltonian path (a path visiting every vertex once, but not returning to the start).
Comparison Cheat-Sheet
• Eulerian: Must traverse every EDGE once. Determined easily by checking if vertex degrees are all even.
• Hamiltonian: Must visit every VERTEX once. Warning: Unlike Eulerian graphs, there is no simple rule based solely on vertex degrees to identify Hamiltonian graphs.
Key Takeaway
Remember: Eulerian = Edges (all degrees even). Hamiltonian = Houses/vertices (visit every vertex once).
6. Planar Graphs and Euler's Formula
What is a Planar Graph?
A graph is called planar if it can be drawn in a single plane (on flat paper) such that no two edges cross each other.
Note: A graph may be drawn with crossing lines initially, but if it is possible to redraw it without crossings, it is still planar!
Euler's Formula for Planar Graphs
When a connected planar graph is drawn without any edge crossings, it divides the plane into separate regions called faces (or regions), denoted by \(F\). This includes the infinite outer face surrounding the entire graph.
For any connected planar graph with \(V\) vertices, \(E\) edges, and \(F\) faces:
\(V - E + F = 2\)
Worked Example: Using Euler's Formula
Question: A connected planar graph has 6 vertices and divides the plane into 5 faces (including the exterior face). How many edges does the graph have?
Step 1: Write down Euler's Formula:
\(V - E + F = 2\)
Step 2: Substitute the known values \(V = 6\) and \(F = 5\):
\(6 - E + 5 = 2\)
\(11 - E = 2\)
Step 3: Solve for \(E\):
\(E = 11 - 2 = 9\)
The graph has 9 edges.
Famous Non-Planar Graphs
Two essential non-planar graphs to recognise are:
1. \(K_5\) (The complete graph on 5 vertices).
2. \(K_{3,3}\) (The complete bipartite graph with 3 vertices in each set, often known as the "utilities problem": connecting 3 houses to gas, water, and electricity without crossing pipes).
Key Takeaway
For any connected planar graph, \(V - E + F = 2\). Always count the outer bounding region as one of the faces.
7. Matrix Representation of Graphs
Computers cannot "look" at a graph drawing, so we represent graphs using matrices.
A. Adjacency Matrix
An adjacency matrix records the number of edges connecting pairs of vertices.
• Rows and columns are labelled with the graph's vertices.
• The entry in row \(i\) and column \(j\) represents the number of direct edges between vertex \(i\) and vertex \(j\).
• For an undirected graph, the adjacency matrix is always symmetric across the leading diagonal.
• For simple graphs, the leading diagonal consists entirely of 0s (since there are no self-loops).
B. Distance (or Weight) Matrix
In a weighted network (where edges have numerical weights such as distances, costs, or travel times), a distance matrix stores the weight of the direct edge between each pair of vertices.
• If no direct edge exists between two distinct vertices, we enter \(\infty\) (or a dash/blank).
• The distance from any vertex to itself is \(0\).
Key Takeaway
An adjacency matrix counts direct connections between vertices (0, 1, 2, ...), while a distance matrix records the direct edge weights between vertices.
Quick Revision Checklist
Before sitting your AS 2 Discrete Mathematics exam, make sure you can confidently:
• State and apply the Handshaking Lemma: \(\sum \deg(v) = 2E\).
• Calculate the number of edges in complete graphs (\(K_n\)) and complete bipartite graphs (\(K_{m,n}\)).
• Recall that a tree with \(n\) vertices has \(n - 1\) edges and no cycles.
• Distinguish clearly between walks, trails, paths, and cycles.
• Identify Eulerian (all degrees even) and semi-Eulerian (exactly two odd degrees) graphs.
• Use Euler's formula \(V - E + F = 2\) for connected planar graphs.
• Construct and interpret adjacency and distance matrices.