Special graphs
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 vertices has exactly edges and one path between any two vertices.
- The complete graph has edges.
- The complete bipartite graph has edges.
- A complement has and .
- 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.
- Handshaking lemma number of edges
Worked example
A simple graph has 5 vertices with degrees . How many edges does it have?
- 1
Add the degrees: .
- 2
This counts every edge twice, so halve it: .
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 vertices always has exactly 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 vertices there are exactly 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 edges must contain a cycle.
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 has edges.
A complete graph is a simple graph on vertices in which every pair of vertices is joined by an edge. Each vertex has degree , so the number of edges is .
Every simple graph on vertices has at most edges.
| Vertices | 4 | 5 | 6 |
|---|---|---|---|
| Degree of each vertex | 3 | 4 | 5 |
| Edges | 6 | 10 | 15 |
- Vertices:
- 4
- Degree of each vertex:
- 3
- Edges:
- 6
- Vertices:
- 5
- Degree of each vertex:
- 4
- Edges:
- 10
- Vertices:
- 6
- Degree of each vertex:
- 5
- Edges:
- 15
How many edges does 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 the sets have and vertices and every vertex of one set is joined to every vertex of the other, so there are edges.
Vertices in the -set have degree , and vertices in the -set have degree .
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 of a simple graph has the same vertices, and two vertices are adjacent in exactly when they are not adjacent in .
So and together make up . The complement of has no edges.
- Edges
- Degrees
Worked example
is a simple graph with 5 vertices and 4 edges. How many edges does have?
- 1
has edges.
- 2
and together make , so .
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 is the number of edges joining vertex to vertex . For a simple graph every entry is or , the diagonal is all and the matrix is symmetric.
A bipartite graph, with vertices ordered by set, has two zero blocks on the leading diagonal. For :
Row and entry sums
- Row sums give the degrees
- All entries add to twice the number of edges
Complete graph
- 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
is a simple graph with vertices and edges. Vertex of has degree . Find the number of edges of the complement and the degree of in .
[3 marks]
- [1] has edges.
- [1] has edges.
- [1]Degree of in is .
That's the notes covered.
Carry on to the next subtopic.
Try a question
How many edges does the complement of have?
1 mark, marked against the mark scheme
How many edges does the complement of have?
1 mark, marked against the mark scheme