Introduction to Graph Theory
Welcome to Graph Theory! If you have ever looked at a subway map, used a GPS app to find the fastest route home, or browsed friends on social media, you have already interacted with graph theory. In decision mathematics, a graph is not a curve plotted on \(x\)- and \(y\)-axes; instead, it is a mathematical structure made up of dots and lines used to model relationships and networks.
Don't worry if this seems like a completely new branch of mathematics. Graph theory is visual, logical, and very intuitive once you get the hang of the core vocabulary.
1. The Fundamental Building Blocks
Let's begin with the basic elements that make up every graph.
Key Definitions
Vertex (plural: Vertices) or Node: A point representing an object (such as a city, a person, or a computer). We usually label vertices with capital letters like \(A, B, C\).
Edge or Arc: A line or curve connecting two vertices, representing a relationship or link between them (such as a road, a friendship, or a cable). An edge connecting vertex \(A\) and vertex \(B\) is written as \(AB\).
Loop: An edge that starts and finishes at the exact same vertex.
Multiple Edges: Two or more edges connecting the same pair of vertices.
Simple Graph: A graph that contains no loops and no multiple edges.
Degree (or Valency) of a Vertex
The degree (or valency) of a vertex is the number of edge ends attached to it. We write the degree of vertex \(v\) as \(\text{deg}(v)\) or \(d(v)\).
Important Rule for Loops: A loop contributes 2 to the degree of its vertex because the edge leaves and returns to that same vertex.
Vertices can be classified based on their degree:
• An even vertex has an even degree (e.g., \(2, 4, 6\)).
• An odd vertex has an odd degree (e.g., \(1, 3, 5\)).
• An isolated vertex has a degree of \(0\).
The Handshaking Lemma
One of the most famous fundamental theorems in graph theory states:
"The sum of the degrees of all vertices in any graph is equal to twice the number of edges."
\(\sum \text{deg}(v) = 2E\)
where \(E\) is the total number of edges in the graph.
Analogy: Think of edges as handshakes between two people. Every time a handshake occurs, two hands are involved. Therefore, the total number of hands shaken must always be double the total number of handshakes.
Vital Consequence: Because \(2E\) is always an even number, the sum of the degrees in any graph must be even. This leads to a golden rule: Every graph must have an even number of odd vertices.
Common Mistake to Avoid: If an exam question asks whether a graph can have vertices with degrees \(3, 3, 3, 2\), the answer is no, because there are three odd vertices (an odd number of odd vertices), which is impossible!
Key Takeaway: A simple graph has no loops or multiple edges. Sum of degrees \(= 2 \times \text{number of edges}\), meaning you can never have an odd number of odd vertices.
2. Types of Graphs
Connected vs Disconnected Graphs
A graph is connected if there is a route along the edges between every pair of vertices. If any vertex or group of vertices is cut off with no pathway to the rest, the graph is disconnected.
Subgraphs
A subgraph is simply a part of a larger graph. It consists of a subset of the original graph's vertices and a subset of its edges.
Complete Graphs (\(K_n\))
A complete graph is a simple graph where every single vertex is directly connected by an edge to every other vertex.
A complete graph with \(n\) vertices is denoted by \(K_n\).
• Each vertex in \(K_n\) has degree \(n - 1\).
• The total number of edges in \(K_n\) is given by the formula: \(E = \frac{n(n - 1)}{2}\).
Example: In \(K_5\) (a complete graph with \(5\) vertices), the number of edges is \(\frac{5(4)}{2} = 10\), and every vertex has degree \(4\).
Bipartite Graphs and Complete Bipartite Graphs (\(K_{r, s}\))
A bipartite graph is a graph whose vertices can be divided into two distinct sets, \(X\) and \(Y\), such that every edge connects a vertex in \(X\) to a vertex in \(Y\). No edges can connect vertices within the same set.
A complete bipartite graph, denoted \(K_{r, s}\), is a bipartite graph where every vertex in the first set of size \(r\) is connected to every vertex in the second set of size \(s\).
• Total vertices: \(r + s\)
• Total edges: \(r \times s\)
Real-world Example: Matching \(r\) job applicants to \(s\) job vacancies where connections only exist between applicants and jobs.
Directed Graphs (Digraphs) and Weighted Graphs
Directed Graph (Digraph): A graph where the edges have arrows indicating a specific one-way direction.
Weighted Graph (or Network): A graph where each edge is assigned a numerical value (a weight). These weights can represent distances, costs, times, or capacities.
Key Takeaway: Complete graphs \(K_n\) have all possible connections (\(\frac{n(n-1)}{2}\) edges). Bipartite graphs divide vertices into two independent sets with connections only running between the sets.
3. Moving Around a Graph: Terminology
Students often mix up the terms used to describe journeys through a graph. Let's make the distinctions crystal clear:
Walk: Any sequence of connected edges. You are allowed to repeat vertices and repeat edges.
Trail: A walk in which no edge is repeated (vertices may still be revisited).
Path: A walk in which no vertex is repeated (and consequently, no edge is repeated).
Cycle (or Circuit): A closed path where the start vertex and end vertex are the same, but no other vertices or edges are repeated.
Memory Trick:
• Path = People (no repeated vertices/people)
• Trail = Tracks (no repeated edges/tracks)
Key Takeaway: Walks are general; trails never repeat edges; paths never repeat vertices; cycles are paths that loop back to the start.
4. Eulerian and Hamiltonian Graphs
Two of the most important concepts in decision mathematics involve finding special routes through graphs.
Eulerian Graphs (Focus on EDGES)
An Eulerian trail is a trail that visits every edge of a graph exactly once.
• Eulerian Graph: A connected graph that contains a closed trail visiting every edge exactly once and returning to the starting vertex. This is possible if and only if every vertex has an even degree.
• Semi-Eulerian Graph (Traversable): A connected graph that contains an open trail visiting every edge exactly once, starting at one vertex and ending at a different vertex. This is possible if and only if there are exactly two odd vertices (the route must start at one odd vertex and finish at the other).
Did you know? This concept originates from the famous Seven Bridges of Königsberg problem solved by Leonhard Euler in 1736, which founded the field of graph theory!
Hamiltonian Graphs (Focus on VERTICES)
A Hamiltonian cycle is a cycle that visits every vertex of a graph exactly once and returns to the starting vertex.
• Hamiltonian Graph: A graph that contains a Hamiltonian cycle.
• Semi-Hamiltonian Graph: A graph that contains a Hamiltonian path (visits every vertex once without repeating), but cannot return to the start vertex to form a cycle.
Eulerian vs. Hamiltonian: Quick Comparison
• Eulerian: Focuses on covering every Edge. Easy to test using vertex degrees!
• Hamiltonian: Focuses on visiting every Head/Vertex. No simple test based purely on degrees exists; you have to inspect the graph carefully.
Key Takeaway: Eulerian = every edge once (all even degrees = full cycle; 2 odd degrees = path). Hamiltonian = every vertex once.
5. Trees and Spanning Trees
What is a Tree?
A tree is a connected simple graph that contains no cycles.
Fundamental Properties of Trees
For any tree with \(n\) vertices (where \(n \ge 1\)):
1. It has exactly \(n - 1\) edges: \(E = V - 1\).
2. There is exactly one unique path between any pair of vertices.
3. Removing any edge disconnects the tree.
4. Adding any single new edge between existing vertices creates exactly one cycle.
Spanning Trees
A spanning tree of a connected graph \(G\) is a subgraph that is a tree and includes all the vertices of \(G\).
If a graph has \(n\) vertices, any spanning tree of that graph will have exactly \(n - 1\) edges.
Application: Spanning trees are used to design minimal infrastructure networks, like connecting towns with the least amount of fiber optic cable.
Key Takeaway: A tree is connected with no cycles. If it has \(n\) vertices, it must have \(n - 1\) edges.
6. Planar Graphs and Euler's Formula
What is a Planar Graph?
A planar graph is a graph that can be drawn in a single plane (on flat paper) in such a way that no edges cross each other.
A graph may initially look non-planar because some lines cross, but if you can redraw it so that the edges meet only at vertices, it is planar.
Faces (or Regions) and Euler's Formula
When a connected planar graph is drawn without crossing edges, it divides the plane into distinct regions called faces (\(F\)).
Crucial Note: Always count the unbounded outer region surrounding the entire graph as one of the faces!
Euler's Formula for Planar Graphs
For any connected planar graph:
\(V - E + F = 2\)
where:
• \(V\) is the number of vertices
• \(E\) is the number of edges
• \(F\) is the number of faces (including the exterior face)
Step-by-Step Example
Consider a simple square graph (4 vertices forming a closed loop with 4 edges):
• Number of vertices \(V = 4\)
• Number of edges \(E = 4\)
• Number of faces \(F = 2\) (1 inside region + 1 outside region)
• Check with Euler's formula: \(V - E + F = 4 - 4 + 2 = 2\). The formula holds!
Key Takeaway: Planar graphs can be drawn without edge crossings. Always remember to count the infinite outside area as a face when using \(V - E + F = 2\).
7. Matrix Representation of Graphs
Computers cannot "look" at graph diagrams, so we represent graphs algebraically using matrices.
Adjacency Matrix
An adjacency matrix records the number of direct edges connecting pairs of vertices.
• Rows and columns are labelled by the vertices.
• The entry in row \(i\), column \(j\) represents the number of edges connecting vertex \(i\) to vertex \(j\).
• For an undirected graph, the adjacency matrix is always symmetric along the leading diagonal.
• For a simple graph, the leading diagonal consists entirely of zeros (since there are no loops).
Distance (or Weight) Matrix
A distance matrix records the weights of the edges between connected vertices.
• If two vertices are directly connected, the entry is the weight of that edge.
• If a vertex is compared to itself on the diagonal, the value is usually \(0\) or represented by a dash \((-)\).
• If there is no direct edge between two distinct vertices, the entry is written as \(\infty\) or left blank with a dash \((-)\).
Key Takeaway: Adjacency matrices record edge counts between vertices; distance matrices record the weights/lengths of those edges.
Quick Summary & Exam Checklist
Before sitting your exam, make sure you can:
• Use the Handshaking Lemma (\(\sum \text{deg}(v) = 2E\)) to prove edge counts or identify impossible graphs.
• State properties of complete graphs \(K_n\) and bipartite graphs \(K_{r, s}\).
• Test for Eulerian graphs (all even vertices) and Semi-Eulerian graphs (exactly 2 odd vertices).
• Identify trees and calculate their edges using \(E = V - 1\).
• Apply Euler's Planar Formula (\(V - E + F = 2\)), remembering to include the outer face.
• Construct and interpret adjacency and distance matrices accurately.