DA5 - Complete and bipartite graphs

Complete and bipartite graphs

Five people each shake hands once with every other person. How many handshakes take place? A graph with one vertex per person and one edge per handshake prevents us counting the same handshake twice.

The complete graph $K_n$ is the simple graph on $n$ vertices in which every pair is adjacent. Each vertex has degree $n-1$. Counting all degrees gives $n(n-1)$, but each edge occurs at both endpoints, so

This formula is not printed in the exam formula booklet. It counts unordered pairs of distinct vertices. No self-handshakes or repeated handshakes are included.

[DIAGRAM: asset_name: Complete and complete bipartite graphs; asset_slug: aqa7367-complete-bipartite; caption: K5 joins every pair while K2,3 joins every pair across its two groups; description: Left is K5 on labelled vertices A B C D E with ten edges. Right is K2,3 with left group A B and right group X Y Z, all six cross-group edges and no within-group edge. Edge crossings have no vertex dots and are not vertices.]

A graph is bipartite if its vertices can be divided into two disjoint sets so that every edge goes from one set to the other. Edges within either set are forbidden; some cross-group pairs may be missing. The complete bipartite graph $K_{r,s}$ includes every cross-group pair, giving $r+s$ vertices and $rs$ edges. The $r$ vertices in the first set each have degree $s$; those in the second each have degree $r$.

A square A–B–C–D–A is bipartite with groups $\{A,C\}$ and $\{B,D\}$, even if drawn without two visible columns. A triangle is not: once A is in one group, both B and C must be in the other, contradicting their edge BC. More generally, following a cycle alternates groups, so a bipartite graph cannot contain an odd-length cycle. The converse holds too: attempt to place vertices by even or odd distance from a starting vertex in each component; a conflict would produce an odd cycle. Thus bipartite graphs are exactly the graphs with no odd cycle.

Keep five vertices but change the allowed connections to two groups of sizes two and three.

The word complete in these two names has a different set of allowed pairs: $K_{2,3}$ is complete bipartite, but is not the complete graph $K_5$.

Use fresh group sizes for the count.

Adjacency matrices

An adjacency matrix stores connections using a fixed order of vertices, so it gives an exact description even when a drawing is crowded.

For a simple undirected graph with vertices in the order A, B, C, D, use the same order for rows and columns. The entry $a_{ij}$ is 1 when row vertex $i$ is adjacent to column vertex $j$, and 0 otherwise. Every diagonal entry is zero because there are no loops. The matrix is symmetric because AB and BA describe the same undirected edge. A row sum is the degree of that vertex, and the sum of all entries is $2E$.

Add only the edge DA. Exactly two matrix entries change, since each undirected edge has two positions.

For a directed graph the row-to-column convention records direction: $a_{ij}=1$ represents an arrow from $i$ to $j$, so symmetry need not hold. Row sums count out-degrees and column sums in-degrees. Multiple edges and loops require an explicitly stated counting convention; do not silently assume that a 0–1 matrix encodes them. Here our calculations use simple undirected graphs.

Changing the vertex order permutes rows and columns together; it changes the displayed matrix without changing the graph. If a bipartite graph is ordered with one group first and the other second, the two within-group diagonal blocks are zero.

Decode this new matrix directly.

The complement of a graph

The complement keeps all the vertices and replaces the edge set by exactly the pairs that were missing.