Lesson 2: Types of graphs and network diagrams
A round-robin competition as a complete graph
SkillsTypes of graphsDrawing network diagrams
Worked example
Six schools — Ashgrove, Bardon, Chermside, Durack, Everton Park and Ferny Grove — enter a futsal round-robin, in which every school plays every other school once.
(a) Each school is a vertex and each game is an edge. What kind of graph models the draw?
(b) How many games are played?
(c) The results are recorded as a digraph with an arrow from the winner to the loser. There are no draws. How many arrows does the digraph have, and what is the total number of wins?
Step 1: Identify the graph
Every pair of schools is joined by exactly one game, and no school plays itself. That is the complete graph on 6 vertices, .
Step 2: Count the games from each school's point of view
Each school plays the other 5, so every vertex has degree 5 and the degree total is .
Step 3: Halve the total
Each game was counted twice, once by each school, so there are games.
This is the complete-graph formula with .
Step 4: Turn the games into arrows
Every game has exactly one winner, so each of the 15 edges becomes one arrow from winner to loser: 15 arrows. Each arrow leaving a vertex is one win, so the wins add to 15.
Answer
(a) The complete graph . (b) 15 games. (c) 15 arrows, and the wins add to 15.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
A round-robin of teams is modelled by the complete graph .
Number of games .
The results digraph has one arrow per game, from the winner to the loser.
Watch out for
counts every game twice. Halve it.
Putting arrows at both ends of an edge: each game has one winner, so it gets one arrow.