Graphs and Networks

Welcome to the World of Graphs and Networks!

In this chapter, we are stepping away from the standard \(y = f(x)\) graphs you've seen since GCSE. Instead, we are looking at Graphs as a way to model the real world. Think of a subway map, a social media friend group, or the circuit board inside your phone—these are all networks! We use Discrete Mathematics to study how things are connected, how to find the best routes, and how to represent complex systems simply. Don't worry if it feels like a lot of new words at first; once you see the patterns, it becomes a very visual and logical part of Further Maths.

1. The Building Blocks: Terminology and Notation

Before we can solve complex problems, we need a common language. A graph is essentially a collection of "dots" and "lines."

Key Terms:

• Vertex (or Node): The "dots" in the graph. These represent objects (like cities, people, or computers). The plural is vertices.
• Arc (or Edge): The "lines" connecting the vertices. These represent the relationships or routes between objects.
• Degree (or Valency) of a Vertex: The number of arcs that meet at that vertex. Think of this as how many "friends" a vertex has.
• Incident: An arc is "incident" to a vertex if it is physically connected to it.
• Adjacent: Two vertices are "adjacent" if there is an arc directly connecting them. Similarly, two arcs are "adjacent" if they share a common vertex.

Quick Tip: In any graph, the sum of the degrees of all vertices is always double the number of arcs. This is because every arc has two ends! This is often called the Handshaking Lemma.

Summary Takeaway: Vertices are the "where," and Arcs are the "how they connect."

2. Describing the Graph's Personality

Not all graphs are the same. We use specific names to describe how "connected" or "simple" they are.

Types of Graphs:

• Simple Graph: A graph with no loops (an arc starting and ending at the same vertex) and no multiple arcs (more than one arc between the same two vertices).
• Connected Graph: You can get from any vertex to any other vertex by following the arcs. There are no "isolated" islands.
• Simply Connected: In discrete maths, this often refers to a graph that is connected and has no cycles (like a tree).
• Tree: A connected graph with no cycles. Analogy: Like a family tree, there are no "loops" where you can circle back to where you started.

Did you know? A tree with \(n\) vertices always has exactly \(n - 1\) arcs. If you add one more arc, you've created a cycle!

3. Routes, Trails, and Cycles

How do we move through a graph? The syllabus distinguishes between different types of "journeys." Don't worry if these seem tricky; just remember the "hierarchy" of movement:

• Walk: The most basic movement. You can go over any vertex or arc as many times as you like.
• Trail: A walk where no arcs are repeated. (You can visit the same vertex twice, though!)
• Path: The "strictest" route. A trail where no vertices are repeated.
• Cycle: A "closed path." You start and end at the same vertex without repeating any other vertices or arcs.
• Route: A general term that could be any of the above.

Common Mistake: Students often mix up Path and Trail. Remember: Path = No People (vertices) repeated. Trail = No Tracks (arcs) repeated.

4. Special Graph Families

Some graphs have very specific structures that we use as benchmarks in Discrete Maths.

Complete Graphs (\(K_n\))

A graph where every single vertex is connected to every other vertex. We use the notation \(K_n\), where \(n\) is the number of vertices.

Important Formula: The number of arcs in a complete graph \(K_n\) is: \( \frac{1}{2}n(n-1) \).

Bipartite Graphs (\(K_{m,n}\))

In a bipartite graph, the vertices are split into two distinct sets. Arcs only connect vertices in one set to vertices in the other set. There are no connections within the same set.

• Complete Bipartite Graph (\(K_{m,n}\)): Every vertex in the first set (size \(m\)) is connected to every vertex in the second set (size \(n\)).
• Number of Arcs: For \(K_{m,n}\), the number of arcs is simply \( m \times n \).

Quick Review: How do you prove a graph is bipartite? Try the Colouring Argument. If you can colour every vertex either Red or Blue so that no two vertices of the same colour are connected, the graph is bipartite!

5. Traversability: Eulerian and Hamiltonian

This is a classic exam topic. It asks: "Can we visit everything in one go?"

Eulerian Graphs (Focus on Arcs)

An Eulerian graph is one where you can find a route that traverses every arc exactly once and returns to the start.

• Eulerian: All vertices have an even degree.
• Semi-Eulerian: Exactly two vertices have an odd degree. You can traverse every arc, but you will start at one odd vertex and end at the other.

Hamiltonian Graphs (Focus on Vertices)

A Hamiltonian Cycle is a cycle that visits every vertex exactly once (and returns to the start).

• Ore's Theorem: For a simple graph with \(n \ge 3\) vertices, if for every pair of non-adjacent vertices \(v\) and \(w\), \( \text{deg } v + \text{deg } w \ge n \), then the graph is Hamiltonian.
• Caution: Ore's Theorem is sufficient but not necessary. If the condition isn't met, the graph might still be Hamiltonian!

Summary Takeaway: Eulerian = Arcs. Hamiltonian = Vertices.

6. Digraphs and Isomorphism

Digraphs (Directed Graphs)

In a digraph, arcs have arrows! They are one-way streets. Instead of just "degree," we use:

• Indegree: Number of arcs pointing into the vertex.
• Outdegree: Number of arcs pointing away from the vertex.

Isomorphism

Two graphs are isomorphic if they are essentially the same, even if they are drawn differently. They must have the same number of vertices, same number of arcs, and the same degree sequence (the list of degrees in order).

Warning: Having the same degree sequence is necessary but not sufficient. You must check that the actual connections are identical!

7. Planar Graphs: Staying Flat

A graph is planar if it can be drawn without any arcs crossing each other.

Key Concepts:

• Subdivision: Adding a new vertex of degree 2 into an existing arc (like adding a bead to a string).
• Contraction: Shrinking an arc until the two vertices at its ends merge into one.
• Euler’s Formula: For any connected planar graph: \( V + R = E + 2 \), where \(V\) is vertices, \(R\) is regions (including the infinite area outside), and \(E\) is edges (arcs).
• Kuratowski's Theorem: A graph is planar if and only if it doesn't contain a subgraph that is a subdivision of \(K_5\) or \(K_{3,3}\). (These two are the "forbidden" non-planar shapes!).
• Thickness: The minimum number of planar graphs needed to "cover" all the edges of a non-planar graph. (For your syllabus, we mostly look at thickness 1 or 2).

8. Networks and Matrices

A Network is just a graph where the arcs have weights (numbers representing distance, cost, or time).

Representing Graphs Numerically:

• Adjacency Matrix: A table where the rows and columns represent vertices. A '1' means they are connected; a '0' means they aren't. For digraphs, this shows the direction.
• Weighted Matrix: Similar to an adjacency matrix, but instead of '1', you write the weight of the arc. If there is no connection, we often use a dash (\(-\)) or an infinity symbol (\(\infty\)).

Quick Review Box:
- Vertex: The point.
- Arc: The line.
- Tree: No cycles.
- Eulerian: Every edge once (Even degrees).
- Hamiltonian: Every vertex once.
- Euler's Formula: \( V + R = E + 2 \).

Final Encouragement

Discrete Mathematics is often about "playing" with the diagrams. If a concept feels abstract, try drawing it! Use different colours for bipartite graphs or trace Eulerian trails with your finger. You’ve got this!