A graph is connected if there is a path between every pair of vertices. If any vertex cannot be reached from another, the graph is disconnected.
Test: Can you trace a route from any vertex to any other vertex, following edges?
A complete graph $K_n$ has every pair of vertices connected by exactly one edge. The number of edges in $K_n$ is:
$$\text{Edges in } K_n = \frac{n(n-1)}{2}$$
| $n$ | Edges |
|---|---|
| 3 | 3 |
| 4 | 6 |
| 5 | 10 |
$K_4$: every vertex connects to all 3 others; each vertex has degree 3.
A bipartite graph has vertices divided into two disjoint sets $U$ and $V$ such that every edge connects a vertex in $U$ to a vertex in $V$ (no edges within a set).
Complete bipartite $K_{m,n}$: every vertex in $U$ connects to every vertex in $V$.
Example: $K_{2,3}$ — 2 teachers each connected to 3 students; \$2 \times 3 = 6$ edges.
A planar graph can be drawn on a flat surface with no edges crossing.
Euler’s formula for connected planar graphs:
$$V - E + F = 2$$
where $V$ = vertices, $E$ = edges, $F$ = faces (including the outer infinite face).
A connected planar graph has 6 vertices and 9 edges. How many faces?
$$F = 2 - V + E = 2 - 6 + 9 = 5 \text{ faces}$$
A tree is a connected graph with no cycles. Properties:
- A tree with $n$ vertices has exactly $n - 1$ edges
- There is exactly one path between any two vertices
- Removing any edge disconnects the tree
A spanning tree of a graph is a tree that includes every vertex of the original graph.
| Type | Key Property |
|---|---|
| Connected | Path exists between every pair |
| Complete $K_n$ | Every pair connected; $\frac{n(n-1)}{2}$ edges |
| Bipartite | Two sets; edges only between sets |
| Planar | Can be drawn without crossings; $V-E+F=2$ |
| Tree | Connected, no cycles; $E = V-1$ |
COMMON MISTAKE: Assuming a graph is planar just because the given drawing has crossings. A graph is planar if some drawing exists without crossings.
EXAM TIP: Euler’s formula $V - E + F = 2$ is frequently used in short-answer questions. Memorise it and remember to count the outer (unbounded) face.
