Loops and multiple edges
A graph may contain two kinds of edge that many problems do not want. A loop joins a vertex to itself. Multiple edges are two or more separate edges joining the same pair of vertices.
In the graph below, A has a loop, and two separate edges join B to C. The degrees still follow the handshake lemma: A meets the loop at both ends and AB once, degree 3; B meets AB and both edges to C, degree 3; C meets its two edges to B, degree 2. The total is 3 + 3 + 2 = 8, twice the 4 edges.
The loop at A and the two edges joining B to C are in gold. The degrees 3, 3 and 2 total 8, and there are 4 edges.
Simple graphs
A simple graph has no loops and at most one edge between any pair of vertices. Take away the loop and one of the two edges from B to C, and the graph above becomes simple, with edges AB and BC only.
Its degrees are now 1, 2 and 1, which total 4 = 2 × 2. In a simple graph with n vertices, a vertex can meet at most the n − 1 others, so no degree is more than n − 1.
Many real networks are simple without being told: two people are friends or not, and nobody is their own friend. Others are not: two towns can be joined by two different roads.
The same three vertices with the loop and the second edge gone: a simple graph with 2 edges and degrees 1, 2 and 1.
Complete graphs
A complete graph is a simple graph in which every pair of vertices is joined by an edge. The complete graph on n vertices is written .
has four vertices and 6 edges: the four sides of a square and its two diagonals. Every vertex is joined to the other three, so every degree is 3, and 4 × 3 = 12 = 2 × 6.
has 10 edges. Every vertex is joined to the other four, so every degree is 4, and 5 × 4 = 20 = 2 × 10.
: five vertices, every pair joined. Each vertex has degree 4, and there are 10 edges.
Counting the edges of
Each of the n vertices meets the n − 1 others, so the degrees add to n(n − 1). Each edge is counted at both of its ends, so has edges. For n = 4 that is 4 × 3 ÷ 2 = 6, and for n = 5 it is 5 × 4 ÷ 2 = 10.
Another count gives the same number. Add the vertices one at a time and join each new one to all the vertices already there: the second vertex brings 1 edge, the third 2, the fourth 3, and the nth brings n − 1. So has 1 + 2 + … + (n − 1) edges, and that sum is .
Since a simple graph has at most one edge per pair, no simple graph on n vertices has more than edges. is the simple graph with the most.
The degree of every vertex in is n − 1, and the edges number .
Bipartite graphs
A bipartite graph is one whose vertices split into two sets so that every edge joins a vertex in one set to a vertex in the other. No edge runs inside a set.
In the graph below the sets are A, B, C and X, Y. The degrees are 2, 1 and 2 on the left and 3 and 2 on the right. Each side adds to 5, the number of edges, because every edge has exactly one end on each side. Together the degrees total 10 = 2 × 5.
Join every vertex on the left to every vertex on the right and the graph is complete bipartite. With 3 vertices on one side and 2 on the other that takes 3 × 2 = 6 edges; this graph lacks only BY.
Every one of the 5 edges runs from A, B or C to one of the gold vertices, X and Y. Adding BY would make it complete bipartite, with 3 × 2 = 6 edges.
Odd cycles
A graph does not have to be drawn in two columns to be bipartite. Walk round a hexagon, putting the vertices alternately on one side and the other: A, C and E on one side, B, D and F on the other. Every edge of the hexagon joins neighbors, which are on different sides, so the hexagon is bipartite.
Try the same with a pentagon. Going round, the sides must alternate: A on one side, B on the other, then C, D and E alternating. E lands on the same side as A, and E is joined to A. Any cycle with an odd number of vertices fails in this way, so a graph containing one is not bipartite. A triangle is the smallest case.
A complete graph with 3 or more vertices contains a triangle, so it is never bipartite.
A hexagon with A, C and E in gold and B, D and F plain. Every edge joins a gold vertex to a plain one, so the hexagon is bipartite.
The usual mistakes
Forgetting to halve. n(n − 1) counts each edge of from both ends; for 8 vertices it gives 56, and has 28 edges.
Ignoring a loop or a repeated edge when deciding whether a graph is simple. Either one alone makes it not simple.
Halving the degree total of one side of a bipartite graph. Each edge has one end on each side, so the degrees on one side already count every edge once.
Deciding a graph is bipartite because it has no triangle. A cycle of 5, or of any odd length, also prevents a split.
A league and a timetable
In the first application below, every school in a league plays every other school once, so the matches are the edges of a complete graph. In the second, exams that share a student must go in different sessions, so splitting them into two sessions means finding two sides of a bipartite graph, and a cycle of 5 clashes makes it impossible.
Worked example: A Chess League in Which Every School Plays Every Other School Once, and How Many Schools a Season Can Take
Question In a chess league, every school plays every other school exactly once. (a) This season 8 schools take part. How many matches are played? (b) Next season more schools want to join, but the league can schedule no more than 66 matches. What is the largest number of schools it can take, and how many matches does each school then play?
1.Model the league as a graph: a vertex for each school and an edge for each match. Every pair of schools plays once, so every pair of vertices is joined by one edge: the graph is the complete graph K8.
Each school is a vertex and each match an edge. School A is joined to all 7 others. 2.Each school plays the other 7, so every vertex has degree 7 and the degrees add up to 8 × 7 = 56. Each match is counted by both schools that play it.
Every pair of schools is joined: the complete graph K8. The degrees add up to 8 × 7 = 56. 3.(a) The number of matches is 56 ÷ 2 = 28. This is n(n − 1)2 with n = 8.
(a) 56 ÷ 2 = 28 matches, the 28 edges of K8. 4.For n schools the league needs n(n − 1)2 matches, and this grows as n grows. Try values near the limit: n = 11 gives 11 × 102 = 55, n = 12 gives 12 × 112 = 66 and n = 13 gives 13 × 122 = 78.
With n schools there are n(n − 1)2 matches: 55, 66 and 78 for 11, 12 and 13. 5.(b) With 12 schools the league plays exactly 66 matches, which is no more than the limit, while 13 schools would need 78. The largest number is 12 schools, and each school plays the other 11.
(b) 12 schools, with 66 matches, no more than the limit; each school plays 11.
Answer: (a) 28 matches; (b) 12 schools, each playing 11 matches
Common mistakes
- Answering 8 × 7 = 56 matches. That counts the match between two schools once for each school, so it must be halved.
- Solving n(n − 1) = 66 and finding no whole number. The matches number n(n − 1)2, so the equation is n(n − 1) = 132, which gives n = 12.
More graphs, degree and trees problems, worked step by step →
Worked example: Seven Exams to Be Split Between a Morning and an Afternoon Session, and Which Exams Share a Session with Math
Question A school must hold seven exams, Biology, Chemistry, Economics, French, History, Math and Physics, in two sessions, morning and afternoon. Two exams clash if some student takes both, and exams that clash must be in different sessions. The clashing pairs are Math and Physics, Physics and Chemistry, Chemistry and Biology, Biology and Economics, Economics and Math, History and Physics, History and Biology, and French and Chemistry. (a) Can the seven exams be split between the two sessions? Give the count that settles it. (b) The only student taking both Economics and Math drops Economics, so that clash disappears. Which exams are now in the same session as Math?
1.Model the timetable as a graph: a vertex for each exam and an edge for each clash. A split into two sessions colors each vertex morning or afternoon, with every edge joining two different colors, so the question asks whether the graph is bipartite.
Each exam is a vertex and each clash an edge. Two sessions means two colors, different along every edge. 2.Follow the edges Math–Physics–Chemistry–Biology–Economics–Math. They form a cycle through 5 exams. Going round it, the sessions must alternate: morning, afternoon, morning, afternoon, morning.
Going round the cycle Math, Physics, Chemistry, Biology, Economics, the sessions must alternate. 3.(a) No. The cycle has 5 exams, an odd number, so the alternation puts Economics in the same session as Math, and they clash. A graph with a cycle of odd length is not bipartite.
(a) No: the cycle has 5 exams, an odd number, so Economics and Math land in the same session. 4.Remove the edge Economics–Math. Put Math in the morning. Then Physics goes in the afternoon, Chemistry in the morning, Biology in the afternoon and Economics in the morning.
Without the clash between Economics and Math, alternate from Math along the path. 5.History clashes with Physics and Biology, which are both in the afternoon, so History goes in the morning. French clashes only with Chemistry, so French goes in the afternoon. Every edge now joins a morning exam to an afternoon exam.
History goes in the session that Physics and Biology are not in; French goes opposite Chemistry. 6.(b) Math shares its session with Chemistry, Economics and History, 4 exams in all, while Physics, Biology and French are in the other session. The graph is connected, so once Math's session is fixed every other exam's session is forced, and no other split exists.
(b) Math shares its session with Chemistry, Economics and History.
Answer: (a) No: Math, Physics, Chemistry, Biology and Economics form a cycle of 5 clashes, and a cycle of odd length cannot alternate between two sessions; (b) Chemistry, Economics and History, so that session holds 4 exams with Math
Common mistakes
- Looking only for three exams that all clash with one another and, finding none, deciding that a split is possible. Any cycle of odd length prevents a split, and here the odd cycle has 5 exams.
- Putting History in the afternoon because the morning looks fuller. History clashes with both Physics and Biology, so it must go in the session that neither of them is in.
More graphs, degree and trees problems, worked step by step →