Welcome to the World of Graphs and Networks!

Welcome to one of the most practical and visual chapters in Further Mathematics! In this section of Discrete Mathematics, we aren't dealing with smooth curves or calculus. Instead, we are looking at Graphs and Networks—mathematical maps used to model everything from social media friendships and neural pathways to airline routes and the internet. Don't worry if this seems a bit "different" from the math you've done before; it’s all about logic and connections. Let's dive in!

1. The Building Blocks: Terminology and Notation

Before we can solve complex problems, we need to speak the language of graphs. Think of a graph as a collection of dots connected by lines.

Key Terms

  • Vertex (or Node): A point on the graph. (Plural: Vertices).
  • Arc (or Edge): A line connecting two vertices.
  • Degree (or Order): The number of arcs that meet at a vertex. Analogy: Think of a train station; the degree is the number of tracks leading into it.
  • Incident: An arc is "incident" to a vertex if it is physically attached to it.
  • Adjacent: Two vertices are "adjacent" if there is an arc connecting them directly. Two arcs are adjacent if they meet at a vertex.

Quick Review:
If vertex A is connected to vertex B by one line:
1. A and B are adjacent vertices.
2. The line is incident to both A and B.
3. The degree of A increases by 1.

Types of Graphs

  • Simple Graph: A graph with no loops (an arc starting and ending at the same node) and no multiple edges (two or more arcs between the same two nodes).
  • Connected Graph: A graph where you can reach any vertex from any other vertex by following a series of arcs.
  • Tree: A connected graph with no cycles. It looks a bit like the branches of a tree!
  • Simply Connected: For our purposes, this refers to graphs that don't have "holes" or complicated overlapping connections that prevent them from being treated as a single unit.

Common Mistake to Avoid: Students often think a "Tree" must look like a plant. In math, a tree is just any graph that is connected and has no closed loops!

2. Moving Around: Walks, Trails, and Paths

In graph theory, how we move from A to B matters. We use specific names depending on whether we repeat nodes or edges.

The Route Hierarchy

  • Walk: The most general route. You can go anywhere, repeating any vertices or arcs you like.
  • Trail: A walk where no arcs are repeated. (You can still visit the same vertex twice).
  • Path: A trail where no vertices are repeated. Mnemonic: Path = People. People don't like to be repeated!
  • Cycle: A closed path. You start and end at the same vertex without repeating any other nodes or arcs.
  • Route: A general term for any walk, trail, or path, which can be open (start and end at different spots) or closed (start and end at the same spot).

Key Takeaway: All Paths are Trails, and all Trails are Walks, but it doesn't work the other way around!

3. Special Graphs: \(K_n\) and \(K_{m,n}\)

Some graphs are so common they have their own special names and formulas.

Complete Graphs (\(K_n\))

A Complete Graph is one where every single vertex is connected to every other vertex by exactly one arc. We use the notation \(K_n\), where \(n\) is the number of vertices.

The Magic Formula: A complete graph with \(n\) vertices has \(\frac{1}{2}n(n-1)\) arcs.

Example: In \(K_4\), there are 4 vertices. Arcs = \(\frac{1}{2} \times 4 \times 3 = 6\).

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

A Bipartite Graph is split into two sets of vertices (let's call them Set X and Set Y). Arcs only connect vertices in Set X to vertices in Set Y. No two vertices in the same set are connected to each other.
Analogy: A "Dance Partner" graph where one set is Leaders and the other is Followers.

A Complete Bipartite Graph (\(K_{m,n}\)) has \(m\) vertices in one set and \(n\) in the other, with every possible connection between the two sets.
The Arc Formula: Simply \(m \times n\).

4. Eulerian Graphs: The Art of Traversing

Did you know? This topic started with the "Seven Bridges of Königsberg" problem. People wanted to know if they could walk through the city crossing every bridge exactly once and return home.

  • Eulerian Graph: A graph where every vertex has an even degree. You can traverse every edge exactly once and end up back where you started.
  • Semi-Eulerian Graph: A graph with exactly two vertices of odd degree. You can traverse every edge exactly once, but you must start at one odd vertex and you will finish at the other odd vertex.
  • Neither: If there are more than two odd vertices, you cannot draw the graph without lifting your pen or repeating an edge!

Step-by-Step Check:
1. List the degree of every vertex.
2. Count how many degrees are odd.
3. 0 odd? Eulerian. 2 odd? Semi-Eulerian. More than 2? Impossible to traverse.

5. Isomorphism: Mathematical Identical Twins

Two graphs are Isomorphic if they are essentially the same, even if they are drawn differently. Imagine a graph made of rubber bands; if you can stretch and move the vertices to make one graph look like the other without snapping any connections, they are isomorphic.

How to prove two graphs are Isomorphic:

  • They must have the same number of vertices and arcs.
  • They must have the same degree sequence (an ordered list of the degrees of the vertices).
  • Warning! Having the same degree sequence is necessary but not sufficient. You must also check that the connections between the vertices match up (e.g., if a degree-3 vertex is connected to two degree-2 vertices in Graph A, the same must be true in Graph B).

6. Digraphs and Networks

Sometimes, connections only go one way.

Digraphs (Directed Graphs)

In a Digraph, arcs have arrows showing direction. Analogy: One-way streets in a city.

  • Indegree: Number of arcs pointing into a vertex.
  • Outdegree: Number of arcs pointing out of a vertex.

Networks

A Network is simply a weighted graph. This means each arc has a number (weight) assigned to it, representing things like distance, time, or cost.

7. Representing Graphs: Matrices

Drawing graphs is great, but computers prefer numbers. We use two types of matrices:

  • Adjacency Matrix: Used for graphs. The entry in row \(i\), column \(j\) tells you how many arcs connect vertex \(i\) to vertex \(j\). (Usually 1s and 0s for simple graphs).
  • Weighted Matrix: Used for networks. The entries are the weights of the arcs. If there is no connection, we usually use an infinity symbol (\(\infty\)) or a dash.

Summary Takeaway:
Graphs and networks help us turn real-world relationships into math. Whether you are checking if a graph is Eulerian by looking at vertex degrees, or identifying isomorphic "twins," remember that it's all about how things are connected, not how pretty the drawing is! Don't worry if it feels a bit like a puzzle—that's exactly what it is.