Welcome to the World of Graphs!

In Further Mathematics, when we talk about "Graphs," we aren't talking about the \(x\) and \(y\) axes you used in GCSE. Instead, we are looking at Discrete Mathematics. Imagine a map of the London Underground or a web of friends on social media. These are networks of points connected by lines. That is what a graph is in this context!

In this chapter, we will learn the specific language used to describe these connections and explore the hidden rules that govern how they work. Don't worry if it feels like a lot of new words at first—once you see the patterns, it becomes a very logical and visual part of maths.

1. The Vocabulary of Graphs

To talk like a discrete mathematician, you need to know the "anatomy" of a graph. Let's break down the most important terms.

The Basics

  • Vertex (plural: Vertices): The "dots" or points in the graph. Think of these as cities on a map.
  • Edge: The "lines" connecting the dots. Think of these as the roads between cities.
  • Degree (or Valency): The number of edges meeting at a vertex. If a city has three roads coming out of it, its degree is 3.

Paths and Connections

  • Trail: A sequence of edges where no edge is repeated.
  • Cycle: A closed trail. You start at one vertex, follow a path, and end up back where you started without retracing any edges.
  • Connected Graph: A graph where you can get from any vertex to any other vertex by following edges. There are no "isolated islands."
  • Subgraph: A smaller part of a larger graph. Just like a subset in sets, it’s a selection of some vertices and edges from the original.

Special Features

  • Loop: An edge that starts and ends at the same vertex.
  • Multiple Edges: When two vertices are connected by more than one edge.
  • Simple Graph: A graph with no loops and no multiple edges. It’s the "cleanest" version of a graph.
  • Subdivision: Replacing an edge with two edges and a new vertex in the middle. Imagine putting a new bus stop halfway along a road.

Quick Review Box:
A Vertex is a dot. An Edge is a line. Degree is how many lines hit a dot. A Cycle is a loop-the-loop journey.

2. Trees and Complete Graphs

Some graphs have very specific structures that make them useful for solving problems.

What is a Tree?

In maths, a Tree is a connected graph with no cycles.
Analogy: Think of a family tree. It branches out, but it never loops back on itself to create a circle.

Complete Graphs (\(K_n\))

A Complete Graph is one where 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 each vertex has a degree of 3.

Bipartite Graphs

In a Bipartite Graph, the vertices are split into two separate sets. Edges only connect a vertex from the first set to a vertex in the second set. You can never have an edge connecting two vertices in the same set.
Real-world example: Imagine a set of "Jobs" and a set of "Workers." You connect a worker to a job they are qualified for. You wouldn't connect a job to another job!

Key Takeaway:
Trees have no cycles. Complete graphs (\(K_n\)) are fully connected. Bipartite graphs are like "matching" two different groups.

3. Adjacency Matrices

Sometimes, drawing a graph is messy. We can represent the same information using a grid of numbers called an Adjacency Matrix.

In an adjacency matrix:
1. The rows and columns represent the vertices.
2. The number in the grid tells you how many edges connect those two vertices.

Common Mistake to Avoid:
For a Simple Graph, the leading diagonal (from top-left to bottom-right) will always be all zeros because simple graphs have no loops (a vertex isn't connected to itself).

4. Eulerian and Hamiltonian Graphs

This section is all about "traversability"—can we travel through the graph following specific rules?

Eulerian Graphs

A graph is Eulerian if you can start at a vertex, travel across every single edge exactly once, and return to the start.
The Trick: A connected graph is Eulerian if and only if every vertex has an even degree.

Semi-Eulerian Graphs

If you can travel across every edge exactly once but you end up at a different vertex than where you started, it is Semi-Eulerian.
The Trick: This happens if exactly two vertices have odd degrees (the start and the end nodes).

Hamiltonian Graphs

A Hamiltonian Graph is slightly different. Here, we care about the Vertices, not the edges. A graph is Hamiltonian if there is a cycle that visits every vertex exactly once.
Memory Aid: Eulerian = Edges. Hamiltonian = Homes (Vertices).

Did you know?
The Eulerian problem started with the "Bridges of Königsberg," where people tried to walk across seven bridges without crossing the same one twice. Leonhard Euler proved it was impossible using these exact degree rules!

5. Planarity and Euler’s Formula

A Planar Graph is a graph that can be drawn in such a way that no edges cross each other. Even if the way it's drawn looks messy, if you can rearrange the dots to stop the lines crossing, 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\)

Note: Faces are the enclosed areas created by the edges, plus the infinite area surrounding the whole graph (the "outside" face).

Kuratowski’s Theorem

How do we know for sure if a graph cannot be drawn without edges crossing? Kuratowski discovered that two specific graphs are "non-planar":
1. \(K_5\) (The complete graph with 5 vertices).
2. \(K_{3,3}\) (A bipartite graph with 3 vertices in each set, where everyone is connected to everyone in the opposite set).
Kuratowski's Theorem states that a graph is non-planar if it contains a subdivision of \(K_5\) or \(K_{3,3}\).

6. Isomorphism

Two graphs are Isomorphic if they are effectively the same graph, just drawn differently. They have the same number of vertices, connected in the same way, with the same degrees for each vertex.

How to check if graphs are NOT isomorphic:
If you are asked to prove two graphs aren't the same, look for a "mismatch":
- Do they have a different number of vertices or edges?
- Do they have different degree sequences? (e.g., one has a vertex of degree 4, but the other doesn't).
- Does one have a cycle of length 3 (a triangle) while the other doesn't?

Encouraging Phrase:
Finding isomorphisms can feel like a "Spot the Difference" puzzle. Stay patient and check the connections vertex by vertex!

Summary Checklist

  • Can I define basic terms like degree, trail, and cycle?
  • Do I know that Eulerian means even degrees for all vertices?
  • Can I use \(V + F - E = 2\) for planar graphs?
  • Do I recognize \(K_5\) and \(K_{3,3}\) as the "forbidden" non-planar graphs?
  • Can I explain why a tree has no cycles?