Special graphs

Special graphs

Spec DA5–DA6 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • The handshaking lemma: the degrees add up to twice the number of edges.
  • A tree with nn vertices has exactly n−1n-1 edges and one path between any two vertices.
  • The complete graph KnK_n has n(n−1)2\dfrac{n(n-1)}{2} edges.
  • The complete bipartite graph Km,nK_{m,n} has mnmn edges.
  • A complement has deg⁡G′(v)=n−1−deg⁡G(v)\deg_{G'}(v)=n-1-\deg_G(v) and e(G)+e(G′)=n(n−1)2e(G)+e(G')=\dfrac{n(n-1)}{2}.
  • An adjacency matrix of a simple graph is symmetric with zeros on the diagonal.

Graphs, degrees and simple graphs

The degree of a vertex counts the edges meeting it, and the degrees always add up to twice the number of edges.

A graph has vertices joined by edges. The degree of a vertex is the number of edges meeting it.

A loop joins a vertex to itself and multiple edges join the same pair of vertices more than once. A simple graph has neither. A graph is connected if there is a path between every pair of vertices.

Every edge has two ends, which gives the handshaking lemma.

ABCDE
A simple graph with degrees A 3, B 3, C 2, D 2, E 2. The degrees add to 12, so there are 6 edges.
  • Handshaking lemma∑deg⁡(v)=2×\sum\deg(v)=2\times number of edges

Worked example

A simple graph has 5 vertices with degrees 3,3,2,2,23,3,2,2,2. How many edges does it have?

A simple graph has 6 vertices, each of degree 3. How many edges does it have?

Simple-connected graphs and trees

A tree is a connected graph with no cycles, and a tree on nn vertices always has exactly n−1n-1 edges.

A cycle is a closed path that starts and ends at the same vertex and repeats no other vertex. A tree is a connected graph with no cycles.

For a tree with nn vertices there are exactly n−1n-1 edges, there is exactly one path between any two vertices, and removing any edge disconnects it.

A spanning tree of a connected graph uses all its vertices and enough edges to form a tree. A connected graph with more than n−1n-1 edges must contain a cycle.

ABCDE
A tree with 5 vertices and 4 edges.

A connected graph has 9 vertices and 8 edges. What can you say about it?

Complete graphs

In a complete graph every pair of vertices is joined, so KnK_n has n(n−1)2\frac{n(n-1)}{2} edges.

A complete graph KnK_n is a simple graph on nn vertices in which every pair of vertices is joined by an edge. Each vertex has degree n−1n-1, so the number of edges is n(n−1)2\frac{n(n-1)}{2}.

Every simple graph on nn vertices has at most n(n−1)2\frac{n(n-1)}{2} edges.

ABCD
K4K_4: every pair of the 4 vertices is joined, giving 6 edges.

K4K_4

Vertices:
4
Degree of each vertex:
3
Edges:
6

K5K_5

Vertices:
5
Degree of each vertex:
4
Edges:
10

K6K_6

Vertices:
6
Degree of each vertex:
5
Edges:
15

How many edges does K7K_7 have?

Bipartite graphs

A bipartite graph splits its vertices into two sets so that every edge goes between the sets, never within one.

In a bipartite graph no edge lies within a set. In a complete bipartite graph Km,nK_{m,n} the sets have mm and nn vertices and every vertex of one set is joined to every vertex of the other, so there are mnmn edges.

Vertices in the mm-set have degree nn, and vertices in the nn-set have degree mm.

ABCDE
K3,2K_{3,2}: every left vertex joined to every right vertex, 6 edges.

To test for a bipartite graph, colour a vertex red, its neighbours blue, their neighbours red and so on. If two adjacent vertices ever need the same colour, it is not bipartite. A graph containing a triangle is never bipartite.

Is a graph that contains a triangle bipartite?

The complement of a graph

The complement has the same vertices, and joins exactly the pairs that the original graph does not.

The complement G′G' of a simple graph GG has the same vertices, and two vertices are adjacent in G′G' exactly when they are not adjacent in GG.

So GG and G′G' together make up KnK_n. The complement of KnK_n has no edges.

ABCDEA′B′C′D′E′
G is a path on 5 vertices (4 edges, left). Its complement G′ (right) has the other 6 edges: 4 + 6 = 10 = edges of K₅.
  • Edgese(G)+e(G′)=n(n−1)2e(G)+e(G')=\dfrac{n(n-1)}{2}
  • Degreesdeg⁡G′(v)=n−1−deg⁡G(v)\deg_{G'}(v)=n-1-\deg_G(v)

Worked example

GG is a simple graph with 5 vertices and 4 edges. How many edges does G′G' have?

A simple graph has 6 vertices and 7 edges. How many edges does its complement have?

Adjacency matrices

The adjacency matrix has a row and column for each vertex, and each entry counts the edges between a pair.

In the adjacency matrix entry (i,j)(i,j) is the number of edges joining vertex ii to vertex jj. For a simple graph every entry is 00 or 11, the diagonal is all 00 and the matrix is symmetric.

A bipartite graph, with vertices ordered by set, has two zero blocks on the leading diagonal. For K2,2K_{2,2}:

(0011001111001100)\begin{pmatrix} 0&0&1&1 \\ 0&0&1&1 \\ 1&1&0&0 \\ 1&1&0&0 \end{pmatrix}

1234
The bipartite graph K₂,₂ with parts {1, 2} and {3, 4}: its four edges are the 1s above the diagonal in the matrix.

Row and entry sums

  • Row sums give the degrees
  • All entries add to twice the number of edges

Complete graph KnK_n

  • Every off-diagonal entry is 1
  • Diagonal is 0

Complement

  • Swap 0 and 1 off the diagonal
  • Keep the diagonal 0

The entries of the adjacency matrix of a simple graph on 4 vertices add up to 10. How many edges does the graph have?

Try an exam question

GG is a simple graph with 66 vertices and 88 edges. Vertex vv of GG has degree 22. Find the number of edges of the complement G′G' and the degree of vv in G′G'.

[3 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

How many edges does the complement of GG have?

1 mark, marked against the mark scheme

Revision notes