AI HL · AHL 1
0 of 43 skills done
What is a graph? Vertices, edges and trees
AHL 1.1
Screenshot and video to come
Press a vertex, then another, to add an edge. Press one vertex twice for a loop. Press an edge to remove it. Drag a vertex to move it.
Press a vertex, then another, to add an edge.
In the 1730s the town of Königsberg had seven bridges linking four areas of land: the north bank A, the island B, the south bank C and the east bank D. The graph models the bridges: each area is a vertex and each bridge is an edge. Can you walk across every bridge exactly once?
Have a go first. Then open the working one line at a time.
Edges: AB, AB, BC, BC, AD, BD, CD
Vertices are land, edges are bridges. Two bridges between the same areas are two edges.
A: 3, B: 5, C: 3, D: 3
The degree of a vertex is the number of edges at it. All four degrees are odd.
Four odd vertices: no such walk
In the middle of a walk you go in by one bridge and out by another, so each area visited in the middle uses bridges in pairs. Only the start and the end can have an odd degree. Four odd areas is too many. Euler explained this in 1736, the first problem of graph theory.
The graph shows ferry crossings between six harbours. The number on each edge is the crossing time in minutes. Write down the number of vertices and edges, the degree of D, and the total of the weights.
Have a go first. Then open the working one line at a time.
6 vertices, 8 edges
The harbours are the vertices, the crossings are the edges.
D is joined to A, B and E: degree 3
Count the edges at D.
25 + 30 + 20 + 15 + 22 + 18 + 28 + 12 = 170 minutes
A weight is a number on an edge. Here it is a time. Add every edge once.
Graph H has 6 vertices and 5 edges, as shown. Is H a tree?
Have a go first. Then open the working one line at a time.
6 vertices, 5 edges
A tree on 6 vertices has 6 − 1 = 5 edges, so the count matches. That is not enough.
No: A, B, C are not joined to D, E, F
A tree is connected: there is a route between every pair of vertices.
Yes: A–B–C–A
A tree has no cycle.
H is not a tree
It fails both tests. Having n − 1 edges does not make a graph a tree.
The diagram shows the complete graph K5, in which every vertex is joined to every other by exactly one edge. How many edges does the complete graph K6 have?
Have a go first. Then open the working one line at a time.
In K6 each vertex is joined to the other 5: degree 5
Check with K5: each vertex has degree 4.
6 × 5 = 30
Add the degrees of all six vertices.
30 ÷ 2 = 15 edges
Each edge has two ends, so it was counted twice. In general Kn has \(\frac{n(n-1)}{2}\) edges.
Graph G has two edges joining Q and R. (a) Is G simple? (b) One of the QR edges is deleted to give a subgraph H. Is H simple? Is H a tree?
Have a go first. Then open the working one line at a time.
Two edges join Q and R
A simple graph has no loops and at most one edge between two vertices.
H has 5 vertices and 5 edges
A subgraph uses some of the vertices and edges of G. Now there is one QR edge.
H is connected but P–Q–R–S–T–P is a cycle
A tree on 5 vertices has 4 edges. H has 5.