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:
| \(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:
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?
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.
