Applications: Graphs, Degree and Trees

Draw each member as a vertex and each friendship as an edge. A member's count is then the degree of that vertex. Every edge has two ends, so it adds 1 to two degrees, and the degrees add up to twice the number of edges.

1. Model the club as a graph: a vertex for each member and an edge for each friendship. Each member's count is the degree of their vertex, so the degrees are 4, 3, 3, 2, 2, 2, 2.
2. Add the degrees: 4 + 3 + 3 + 2 + 2 + 2 + 2 = 18. Each friendship joins two members, so it is counted once by each of them and appears twice in this total.
3. (a) The number of friendships is 18 ÷ 2 = 9. Check: the network in the figure fits every count and has 9 edges.
4. For the second club, add the counts in the same way: 5 + 4 + 3 + 3 + 2 + 2 + 2 = 21.
5. (b) No. The degrees of any graph add up to twice the number of edges, which is an even number, and 21 is odd. Put another way, three members give an odd count, and a graph always has an even number of vertices of odd degree.

answer(a) 9 friendships; (b) no: the counts add up to 21, which is odd, but the degrees of a graph always add up to an even number

techniqueVertices, Edges and Degree

Draw each router as a vertex and each cable as an edge, so each planned number is a degree. The graph must be simple, so a router can be joined to each of the other five at most once. The routers with the most cables leave the least choice, so place their cables first.

1. Model the plan as a graph: a vertex for each router and an edge for each cable. At most one cable between two routers and none from a router to itself means the graph is simple, so a degree can be at most 5, the number of other routers.
2. Plan 1 adds up to 5 + 5 + 4 + 2 + 1 + 1 = 18, which is even, so the handshake count alone does not rule it out. Look at the busiest routers instead. P has degree 5, so it is joined to every other router, and so is Q.
3. (a) No. U and V are each joined to both P and Q, so each has at least 2 cables, but plan 1 gives them 1 each. Plan 1 cannot be built.
4. Plan 2: P has degree 5, so join it to all the others, using 5 cables. The degrees still needed are Q 3, R 3, S 2, U 1 and V 1.
5. Join Q to R, S and U, using 3 cables. Still needed: R 2, S 1 and V 1. Join R to S and to V, using 2 cables. Every router now has its planned number.
6. (b) Yes, plan 2 can be built, with 5 + 3 + 2 = 10 cables. Check: the degrees add up to 5 + 4 + 4 + 3 + 2 + 2 = 20, and 20 ÷ 2 = 10.

answer(a) No: P and Q, with 5 cables each, are joined to every other router, so U and V would each have at least 2 cables, not 1; (b) yes, with 10 cables

techniqueVertices, Edges and Degree · Simple, Complete and Bipartite Graphs

Draw each school as a vertex and each match as an edge. Every pair of schools plays once, so every pair of vertices is joined: the graph is complete. Count the edges from the degrees and halve.

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 K₈.
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.
3. (a) The number of matches is 56 ÷ 2 = 28. This is n(n − 1)2 with n = 8.
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.
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.

answer(a) 28 matches; (b) 12 schools, each playing 11 matches

techniqueSimple, Complete and Bipartite Graphs · Vertices, Edges and Degree

Draw each tutor and each student as a vertex and each tutoring pair as an edge. Every edge joins a tutor to a student, so the graph is bipartite, and every edge has exactly one end on each side. The degrees on either side therefore add up to the number of edges.

1. Model the center as a graph: a vertex for each tutor and each student, and an edge for each tutoring pair. Every edge joins a tutor to a student, so the graph is bipartite, with the tutors on one side and the students on the other.
2. Count the edges from the tutors' side. Each edge has exactly one end at a tutor, so the number of edges is the sum of the tutors' degrees: 3 × 4 + 3 × 2 = 12 + 6 = 18.
3. (a) There are 18 tutoring pairs.
4. Count the same edges from the students' side. Each edge has exactly one end at a student, so the students' degrees also add up to 18. The 9 students all have the same degree d, so 9d = 18.
5. (b) d = 18 ÷ 9 = 2, so each student has 2 tutors. Check: the degrees on both sides together add up to 18 + 18 = 36, which is 2 × 18, as the handshake lemma requires.

answer(a) 18 tutoring pairs; (b) 2 tutors each

techniqueSimple, Complete and Bipartite Graphs · Vertices, Edges and Degree

Draw each exam as a vertex and each clash as an edge. A split into two sessions gives every vertex one of two colors, with the two ends of every edge in different colors, which is what it means for the graph to be bipartite. Going round a cycle the colors must alternate, so a cycle of odd length makes a split impossible.

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.
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.
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.
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.
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.
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.

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

techniqueSimple, Complete and Bipartite Graphs

Draw each village as a vertex and each pipe as an edge. With no loop, each group is a tree and the whole graph is a forest. A tree has one edge fewer than it has vertices, so the number of groups is the number of vertices minus the number of edges.

1. Model the network as a graph: a vertex for each village and an edge for each pipe. The groups are the connected components. With no loop, each component is a tree, and the whole graph is a forest.
2. A tree with k vertices has k − 1 edges. Add this over all the components: if c components hold the 10 villages, the number of edges is 10 − c.
3. (a) 10 − c = 6, so c = 4 groups. Check by tracing the pipes: the groups are A, B and C; D and E; F, G, H and I; and J on its own.
4. A new pipe between two different groups joins them into one group, so each pipe reduces the number of groups by at most 1. To go from 4 groups to 1 takes at least 4 − 1 = 3 pipes, and 3 pipes that each join two different groups are enough.
5. (b) The fewest extra pipes is 3, and the finished network has 6 + 3 = 9 pipes. Check: a connected network with no loop on 10 villages is a tree, and a tree with 10 vertices has 10 − 1 = 9 edges.

answer(a) 4 groups; (b) 3 extra pipes, making 9 pipes in all

techniqueSubgraphs, Connectedness and Trees

Draw each town as a vertex and each road as an edge. A road whose closure disconnects the graph is called a bridge. A road that lies on a cycle is never a bridge, because the rest of the cycle is another way round, so look for the roads on no cycle.

1. Model the island as a graph: a vertex for each town and an edge for each road. A road whose removal disconnects the graph is called a bridge. An edge that lies on a cycle is never a bridge, because the rest of the cycle is another way round.
2. Find the cycles. H–A–B–C–H is a cycle of 4 roads, and D–E–F–D is a cycle of 3 roads. That accounts for 7 of the 8 roads.
3. (a) The one road on no cycle is B–D. Removing it leaves two components, H, A, B, C and D, E, F, so the 3 towns D, E and F are cut off from the harbor. Every other road lies on a cycle, so closing it splits nothing.
4. A new road from H to D, E or F makes a cycle that runs along B–D. For example, a road from H to F gives the cycle H–A–B–D–F–H. Then B–D is no longer a bridge, and every other road still lies on its old cycle.
5. H already has roads to A and C, so the only other town to try is B. A road from H to B makes the cycles H–A–B–H and H–B–C–H, but neither passes along B–D, which stays a bridge.
6. (b) The new road could run to D, E or F, 3 possible towns, but not to B.

answer(a) The road between B and D; 3 towns, D, E and F, would be cut off from the harbor; (b) D, E or F, any one of the 3, but not B

techniqueSubgraphs, Connectedness and Trees

Draw each folder or file as a vertex, with an edge from each folder to each item directly inside it. Every item except the top folder has exactly one folder above it, so the graph is a tree rooted at the top folder. Count the edges from the folders, then use the fact that a tree has one more vertex than it has edges.

1. Model the directory as a graph: a vertex for each folder or file, and an edge from each folder to each item directly inside it. Every item except the top folder has exactly one folder above it, so the graph is connected with no cycle: a tree, rooted at the top folder.
2. Count the edges from the folders. Each of the 7 folders has 3 items inside it, so there are 7 × 3 = 21 edges.
3. (a) A tree has one more vertex than it has edges, so the directory holds 21 + 1 = 22 items. The extra 1 is the top folder, the only item that is not inside another folder.
4. (b) The files are the items that are not folders: 22 − 7 = 15 files. They are the leaves of the tree, the vertices of degree 1.
5. Check with the degrees. The top folder has degree 3, each of the other 6 folders has degree 3 + 1 = 4, and each file has degree 1: 3 + 6 × 4 + 15 = 42, which is 2 × 21.

answer(a) 22 items; (b) 15 files

techniqueSubgraphs, Connectedness and Trees · Vertices, Edges and Degree

Draw each junction as a vertex and each street as an arc, an arrow pointing the way traffic flows. Every junction reaching every other is what it means for a directed graph to be strongly connected. A junction with no arc leaving it is a dead end, so start with the out-degrees.

1. Model the streets as a directed graph: a vertex for each junction and an arc for each street, pointing the way traffic flows. Every junction reaching every other is what it means for the graph to be strongly connected.
2. Find each junction's out-degree, the number of arcs leaving it: A 1, B 2, C 2, D 1 and E 0.
3. (a) No. Junction E has out-degree 0, so a driver at E cannot leave it, and the graph is not strongly connected.
4. The reversed street must give E an arc out, or E stays a dead end, so it must be one of the two streets into E: D to E or B to E. Reversing D to E would leave D with no arc out, since D's only street led to E. That leaves B to E.
5. Reverse B to E, so that it runs from E to B. The arcs A to B, B to C and C to A form a cycle, and so do B to C, C to D, D to E and E to B. The two cycles share B and C, so every junction can reach every other.
6. (b) Reverse the street from B to E. Check: from E the route E, B, C, A reaches A, and from A the route A, B, C, D, E reaches E.

answer(a) No: junction E has out-degree 0, so no street leaves it; (b) the street from B to E, which then runs from E to B; no other of the 6 streets works

techniqueDirected Graphs and Strong Connectedness

Draw each player as a vertex and each game as an arc from the winner to the loser. Every pair plays once, so every pair of vertices is joined by exactly one arc, and each player's wins are the out-degree of their vertex. The out-degrees add up to the number of games.

1. Model the league as a directed graph: a vertex for each player and an arc from the winner to the loser of each game. Every pair plays once, so every pair of vertices is joined by exactly one arc. A player's wins are the out-degree of their vertex.
2. There are 5 × 42 = 10 games, one for each edge of K₅, and each game gives exactly one win, so the out-degrees add up to 10.
3. (a) Eve won 10 − (3 + 3 + 2 + 1) = 10 − 9 = 1 game.
4. Draw the arcs that are given. Ben lost only to Ana, so Ben beat Cal, Dee and Eve. Cal lost only to Ana and Ben, so Cal beat Dee and Eve. Dee's one win was against Eve, so Dee lost to Ana, Ben and Cal.
5. Eve has now lost to Ben, Cal and Dee. Her only other game is against Ana, and she won 1 game, so she won that one.
6. (b) Eve beat Ana. Check: Ana then beat Ben, Cal and Dee and lost to Eve, which gives Ana her 3 wins.

answer(a) 1 game; (b) Ana

techniqueDirected Graphs and Strong Connectedness · Simple, Complete and Bipartite Graphs