Graphs and networks

In graph theory a graph is a set of points (vertices) joined by lines (edges). Graphs model networks like roads, friendships and the internet, and algorithms find shortest routes and cheapest connections.

Key facts

  • Degree: the number of edges at a vertex. The sum of degrees = 2 × edges.
  • A tree is connected with no cycles; with n vertices it has n − 1 edges.
  • Dijkstra’s algorithm finds shortest paths.
  • Kruskal’s and Prim’s algorithms find minimum spanning trees.
  • Euler: a route using every edge once exists if 0 or 2 vertices have odd degree.

Worked examples

Example 1

Can you draw this house shape (a square with a triangle on top and both diagonals of the square) without lifting your pen or going over a line?

  1. The two bottom corners have degree 3 (odd); all others are even.
  2. Exactly two odd vertices: possible, starting at one and ending at the other.

Answer: Yes, start at a bottom corner