Course 30.3Lesson 2 of 3
A tree is a connected graph with no cycle; with vertices it has edges and at least two leaves. A graph is bipartite when its vertices split into two parts with every edge going across, which happens exactly when it has no odd cycle. A connected graph has an Euler circuit when every degree is even, and an Euler trail when exactly two degrees are odd.
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.
A family tree, the folders on a computer and the pipes of a water supply branch out without loops. A tree is a connected graph with no cycle. A vertex of degree is a leaf.
Facts about a tree with vertices.
A graph with no cycle that may have several components is a forest. A forest with vertices and components has edges, because each component is a tree.
Cayley's formula. There are different trees on labelled vertices. For that is : the paths and the stars.
A graph is bipartite when its vertices split into two parts, so that every edge joins the two parts. Think of students and clubs, with an edge when a student is in a club. The complete bipartite graph joins each of vertices to each of others. It has edges.
Theorem. A graph is bipartite exactly when it has no cycle of odd length.
Why. Going round a cycle in a bipartite graph, you switch parts at every step, so you return after an even number of steps. Conversely, if there is no odd cycle, colour each vertex by whether its distance from a fixed start is even or odd. No edge then joins two vertices of the same colour.
Mantel's theorem. A graph on vertices with no triangle has at most edges.
Proof. Let have the largest degree . Its neighbours are not joined to each other, or there would be a triangle. So every edge has an end among the other vertices, and each of those has degree at most . Hence , by AM-GM. The bound is reached by when is even.
The town of Königsberg had seven bridges joining four land areas. Can a walk cross every bridge exactly once? In 1736 Euler showed that it cannot, and graph theory began.
An Euler trail uses every edge exactly once. An Euler circuit does so and ends where it started.
Euler's theorem. A connected graph (or multigraph) has an Euler circuit exactly when every degree is even. It has an Euler trail that is not a circuit exactly when it has exactly two odd vertices, and the trail then runs from one odd vertex to the other.
Why the degrees must be even. Each time the walk passes through a vertex, it uses one edge in and one edge out. Only the start and the end can use an odd number of edges.
Why even degrees are enough. Start anywhere and walk along unused edges. You can only get stuck back at the start. If some edges are unused, start a new closed walk at a vertex of the first one and splice it in. This method is called Hierholzer's algorithm.
In Königsberg the four land areas had degrees . Four odd vertices: no Euler trail.
A walk that visits every vertex once is a different question: a Hamilton cycle. No simple test like Euler's is known for it.
The program checks two things about a graph given as a list of edges: whether an Euler circuit or trail exists, and whether the graph is bipartite, by colouring outwards from a vertex.
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…