Topic 3.14: Graph theory (HL only) Questions

In a graph, the degree of a vertex is:

A 'path' through a graph is a route that:

A computer network connects 6 servers with these cables: 1–2, 1–3, 2–3, 3–4, 4–5, 4–6, 5–6. Find the degree of each server, and verify the handshake lemma.

At a conference, 8 delegates each shake hands with exactly 3 others. Modelling this as a graph, find the total number of handshakes (edges).

Which statement about a tree on n vertices is always true?

A water-supply network is connected, has 12 junctions and is a tree (no loops/cycles).

(a) Find the number of pipes (edges).
(b) Explain what removing one pipe does to the supply.

A graph has 4 vertices, each of degree 3. How many edges does it have?

A bipartite graph is one whose vertices can be split into two groups such that:

A school timetable links every one of 7 subjects to every other subject that shares a student, and it turns out every pair shares a student. Modelling subjects as vertices, state which standard graph this is and find the number of edges.

A graph has 5 vertices with degrees 4, 3, 3, 2, 2.

(a) Show this is possible by the handshake lemma and find the number of edges.
(b) State, with a reason, whether the graph could be a tree.

A courier follows the route P → Q → R → P → S along existing roads, using the roads PQ, QR, RP and PS (all different).

Classify this route as precisely as possible (walk, trail, path or cycle), justifying your choice.