Lesson 2: Types of graphs and network diagrams

A round-robin competition as a complete graph

SkillsTypes of graphsDrawing network diagrams

Worked example

  • Simple familiar

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?

1 of 4 steps
  1. 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, K6K_6.

    K6K_6

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. A round-robin of nn teams is modelled by the complete graph KnK_n.

  2. Number of games =n(n−1)2= \frac{n(n-1)}{2}.

  3. The results digraph has one arrow per game, from the winner to the loser.

Watch out for

  • 6×5=306 \times 5 = 30 counts every game twice. Halve it.

  • Putting arrows at both ends of an edge: each game has one winner, so it gets one arrow.

Save your progress with a free account