Welcome to the World of Graphs!
In most of your maths lessons, "graphs" mean \(y = x^2\) or straight lines. But in Discrete Mathematics, graphs are much more like maps or social networks. They are simply sets of "dots" connected by "lines."
By the end of these notes, you’ll be able to describe these diagrams like a pro, understand how to navigate them, and even solve puzzles that have baffled mathematicians for centuries! Don't worry if it feels like a lot of new words at first—we'll take it one step at a time.
1. The Anatomy of a Graph
Before we can do anything clever, we need to know the names of the parts. Think of a graph like a collection of cities and the roads between them.
Key Terms (Syllabus DA1 & DA6)
Vertex (plural: Vertices): These are the "dots." In a real-world example, these could be people in a social network or stations on a train line.
Edge: The "lines" connecting the vertices. They represent a relationship or a path between two points.
Degree (or Valency): The number of edges connected to a specific vertex. Tip: If a vertex has a loop, that loop counts as 2 towards the degree!
Loop: An edge that starts and ends at the same vertex.
Multiple Edges: When there is more than one edge connecting the same two vertices.
Simple Graph: A graph with no loops and no multiple edges. It’s the "cleanest" version of a graph.
Building the Graph
Subgraph: A smaller part of a larger graph. Imagine taking a map of the UK but only looking at the roads in London—that's a subgraph.
Subdivision: This is what happens when you "zoom in" on an edge and place a new vertex in the middle of it, turning one edge into two.
Connected Graph: A graph where you can get from any vertex to any other vertex by following the edges. It doesn't have to be a direct route, but there shouldn't be any "isolated islands."
Quick Review:
- Vertices = Dots
- Edges = Lines
- Degree = Number of lines meeting at a dot
- Simple = No loops or double-lines
2. Moving Around: Trails and Cycles
Now that we have our "map," how do we move through it? (Syllabus DA1)
Trail: A sequence of edges where no edge is repeated. You can visit the same vertex twice, but you can't walk across the same bridge twice!
Cycle: A closed trail. This means you start and end at the same vertex without repeating any edges along the way.
Analogy: Think of a "Trail" like a walk through a park where you want to see every path but never double back on the same path. A "Cycle" is like a lap of a racing track.
3. Eulerian and Hamiltonian Graphs
This is where we start looking at special properties of graphs. These are named after two famous mathematicians, Leonhard Euler and William Rowan Hamilton. (Syllabus DA2)
Eulerian Graphs
An Eulerian graph is one where you can find a trail that uses every single edge exactly once and returns to the start.
The Secret Rule: A connected graph is Eulerian if, and only if, every single vertex has an even degree.
Semi-Eulerian: You can use every edge once, but you start and end at different places. This happens if the graph has exactly two odd vertices (the start and the end).
Hamiltonian Graphs
A Hamiltonian graph focuses on vertices, not edges. It is a graph that contains a cycle that visits every vertex exactly once (and returns to the start).
Memory Aid: Eulerian = Edges. Hamiltonian = Homes (Vertices).
Key Takeaway:
- Eulerian: "Can I draw this without lifting my pen or retracing a line?"
- Hamiltonian: "Can I visit every city once and get back home?"
4. Special Types of Graphs
Some graphs have very specific structures that make them useful for modelling different situations. (Syllabus DA5 & DA6)
Complete Graphs (\(K_n\))
In a complete graph, every vertex is connected to every other vertex by exactly one edge. We use the symbol \(K_n\) where \(n\) is the number of vertices.
Example: In \(K_4\), there are 4 vertices, and every vertex has a degree of 3.
Bipartite Graphs
In a bipartite graph, the vertices are split into two separate sets (let's call them Set A and Set B). Edges only exist between the sets, never within a set.
Real-world example: A graph showing "Students" and "Classes." An edge connects a student to a class they take. Students aren't connected to other students, and classes aren't connected to other classes.
Trees
A Tree is a very simple connected graph that has no cycles.
Did you know? A tree with \(n\) vertices will always have exactly \(n - 1\) edges. If you add even one more edge, you'll create a cycle!
5. Adjacency Matrices and Complements
Sometimes, drawing a graph is messy. We can use a table (matrix) instead. (Syllabus DA5)
Adjacency Matrix: A grid where the rows and columns represent vertices. The number in the grid tells you how many edges connect those two vertices.
Complement of a Graph: Imagine a graph \(G\). The complement (written as \(G'\)) is a graph with the same vertices, but it contains all the edges that weren't in the original graph.
Analogy: If \(G\) represents "People who are friends," the complement \(G'\) represents "People who are strangers."
6. Planar Graphs and Euler's Formula
Can you draw a graph without any edges crossing over each other? (Syllabus DA3)
Planar Graph: A graph that can be drawn in a way that no edges cross. Even if the way it is currently drawn has crossings, if you can "untangle" it, it’s planar.
Euler’s Formula
For any connected planar graph, there is a magic relationship between the number of Vertices (\(V\)), Edges (\(E\)), and Faces (\(F\)):
\(V + F = E + 2\)
What is a "Face"?
Faces are the regions bordered by edges.
Common Mistake: Always remember to count the "infinite" region outside the graph as one of the faces! If you have a square, it has 2 faces: the inside of the square and the massive area outside it.
Quick Example:
A simple triangle has:
- \(V = 3\)
- \(E = 3\)
- \(F = 2\) (the inside and the outside)
Check: \(3 + 2 = 3 + 2\). It works!
Summary Table: Key Properties
Tree: Connected, no cycles, \(E = V - 1\).
Complete (\(K_n\)): Every vertex connected to all others.
Planar: No edges need to cross, follows \(V + F = E + 2\).
Eulerian: All degrees are even.
Bipartite: Vertices in two groups; connections only between groups.
Don't worry if this seems tricky at first! Discrete math is all about visualising the connections. Try drawing these different types of graphs yourself—it's the best way to make the definitions stick!