Graph theory: watch it solved step by step

Degrees, the handshaking lemma, connectedness, trees and Euler paths and circuits, for a list of edges or a complete graph K_n. Level: University. Type any problem of this kind and the Lab works it out and animates every move, with a plain-words explanation of why.

Worked example: K6

1. The graph. A graph is dots (vertices) joined by lines (edges). Here is the one we are given.
2. Degrees. The degree of a vertex is the number of edges that touch it.
3. The handshaking lemma. Every edge has two ends, so the degrees always add up to twice the number of edges. This is why the number of odd-degree vertices is always even.
4. The adjacency matrix. A grid with a 1 where two vertices are joined. It is symmetric, because an edge works both ways.
5. Connected?. A graph is connected if you can get from any vertex to any other along edges. Start at one vertex and spread out.
6. Is it a tree?. A tree is a connected graph with no cycles, which means it has exactly one fewer edge than vertices.
7. Can you trace it without lifting your pen?. An Euler circuit uses every edge exactly once and returns to the start: possible when the graph is connected and every degree is even. An Euler path needs exactly two odd vertices.
8. The conclusion. No Euler path or circuit (6 odd vertices).
9. Check with the formula for K_n. A complete graph joins every pair of vertices, so it has n(n-1)/2 edges.

Answer: 6 vertices, 15 edges; connected; not a tree; no Euler path or circuit (6 odd vertices)

Practise graph theory with problems the Lab marks for you.