Graphs and networks

What is a graph

In this topic a graph (also called a network) is just dots joined by lines: the dots are vertices and the lines are edges. There is only one rule — every edge must end at a vertex at both ends. Everything else is allowed: an edge from a vertex back to itself (a loop), two vertices joined twice (a double edge), edges that cross without meeting, and vertices attached to nothing (isolated).

Position and shape carry no meaning. Only one thing matters: which pairs of vertices are joined. Two graphs with the same structure are called isomorphic — one can be stretched and rearranged into the other without changing any connections.

Degree and connection

The degree of a vertex is the number of edge-ends attached to it. A loop contributes 2 to the degree of its vertex, because both ends arrive there.

A graph is connected if you can travel along edges between any pair of vertices; otherwise it is disconnected, and it splits into pieces called components.

Special graphs

• A cycle is a connected graph where every vertex has degree 2 — the graph of any polygon.
• A star places vertices around a circle and joins each one to the vertex $s$ places along.
• The complete graph $K_n$ joins every pair of $n$ vertices with a single edge, so every vertex has degree $n - 1$.

Solids make graphs too: a cube’s corners and edges form a graph that can be redrawn flat.

The handshaking lemma

Every edge has exactly two ends, so:

$$\text{sum of all degrees} = 2 \times \text{number of edges}$$

This answers counting questions instantly — degrees $2, 3, 3, 5, 7$ sum to 20, so the graph has 10 edges. It also proves impossibilities: the sum of all degrees must be even, so no graph can have degrees $3, 3, 3$, and five people cannot each shake hands exactly five times.

Euler’s formula

A graph is planar if it can be drawn with no crossing edges. Counting the vertices $V$, edges $E$ and faces $F$ of a connected planar graph:

$$V - E + F = 2$$

Exams ask you to verify the formula on a drawing or find a missing value: a connected planar graph with $V = 7$ and $F = 9$ must have $E = 7 + 9 - 2 = 14$. The formula needs the graph connected and actually drawn without crossings — a drawing with crossing edges gives false face counts.