Course 30.3Lesson 1 of 3
A graph is a set of vertices with some pairs joined by edges. The degree of a vertex is the number of edges at it. Every edge has two ends, so the degrees add up to twice the number of edges: the handshake lemma. So the number of odd vertices is always even. Paths, cycles and connected components describe how a graph hangs together.
This lesson is free to read. Enroll free to keep your place and take the tests.
Try the code and the simulations beside the lesson.
Five friends message each other. Draw a dot for each friend and a line between two friends who have exchanged messages. The picture is a graph. The dots are vertices and the lines are edges. Only who is joined to whom matters, not where the dots sit or how the lines bend.
In this chapter a graph is simple: no edge joins a vertex to itself (a loop), and two vertices are joined by at most one edge. A graph that allows several edges between two vertices is called a multigraph. Euler's bridges in the next lesson need one.
The degree of a vertex, written , is the number of edges at it. A vertex of degree is isolated. A graph in which every vertex has the same degree is called -regular.
At a party some guests shake hands. Add up the numbers of handshakes of all the guests. What do you get?
Every handshake involves two people, so it is counted twice. The same holds in any graph.
Handshake lemma. In every graph, , where is the number of edges.
Corollary. The number of vertices of odd degree is even.
Proof. Split the sum of degrees into the even degrees and the odd degrees. The total is even, and so is the sum of the even degrees. So the sum of the odd degrees is even, and a sum of odd numbers is even only when there is an even number of them.
So people cannot each shake hands with exactly others: the degree sum would be , which is odd.
The complete graph joins every two of its vertices. Each vertex has degree , so
The list of degrees, largest first, is the degree sequence. An even sum is needed, but it is not enough. The list has an even sum, yet no simple graph has it. The two vertices of degree would each be joined to all three others, so the last two vertices would have degree at least .
Havel–Hakimi test. Remove the largest degree , and subtract from each of the next degrees. The old list is a degree sequence exactly when the new list is one. Repeat until the answer is clear.
For : remove and subtract from the next three. This gives . A vertex of degree needs two other vertices to join, and here no other vertex can take an edge. So fails.
A graph is connected when there is a path between every two vertices. Otherwise it falls into separate pieces called components.
The program stores a graph as a list of edges. It works out the degrees, checks the handshake lemma, and finds the component of a vertex by searching outwards from it.
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Every lesson is open to read. Enrolling also lets you:
Log in to join the discussion.
Loading…