Lecture notes · Math for Computer Science · Lecture 10

Graph Theory III

MIT 6.042J Mathematics for Computer Science, lecture 10, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part introduces Euler tours, which are walks that use every edge of a graph exactly once, and starts a proof about when such a tour exists.

Key ideas

An Euler tour is a walk that uses every edge of a graph exactly once. A tour also starts and ends at the same vertex. 2:06
The theorem says a connected graph has an Euler tour if and only if every vertex has even degree. This gives a simple way to check a graph. 3:42
The proof has two directions, because 'if and only if' means you must prove both ways. The first direction starts from a graph that already has an Euler tour and shows its degrees are even. 4:08
Each time the tour enters a vertex, it leaves again, so every visit uses two edges. Since each edge is used only once, a vertex's degree is twice the number of times the tour passes through it. 9:08

Words to know

Euler tour: A trip along the lines of a graph that uses every line exactly once and ends back where it started.
vertex: A point in a graph, like a dot or a place.
edge: A line in a graph that joins two vertices.
degree: The number of edges that touch a vertex.

Example

Imagine a set of rooms joined by doors, where each door is a graph edge. An Euler tour is a walk that goes through every door exactly once and ends in the room where you started. Each time you walk into a room, you must walk back out, so each room's doors are used in pairs.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part shows why a connected graph where every vertex has even degree must have an Euler tour, using a proof by contradiction on the longest walk that repeats no edge.

Key ideas

The proof takes the longest walk that never uses the same edge twice. A walk is a path that moves along edges from one vertex to the next. 11:15
If an edge touching the last vertex was not used, you could add it to the walk and make it longer. That would contradict the walk being the longest, so every edge touching the last vertex must be used. 13:37
The walk must start and end at the same vertex. If it did not, the end vertex would have an odd number of used edges, and since all of its edges are used, its total degree would be odd. That breaks the rule that every degree is even. 16:42
Showing the walk goes all the way around is not enough. An Euler tour must use every edge in the graph, so the proof still needs to show that no edge is left out. 18:54
To show every edge is used, the lecturer starts a proof by contradiction, assuming the walk is not an Euler tour, and uses the fact that the graph is connected. 19:14

Words to know

Euler tour: A trip through a graph that uses every edge exactly once and ends where it started.
walk: A route that moves from vertex to vertex along edges, where edges and vertices can repeat.
degree: The number of edges touching a vertex.
incident: Touching. An edge is incident to a vertex if the edge connects to that vertex.

Example

Imagine a mail carrier who must walk every street in a town exactly once and return to the post office. If every intersection has an even number of streets, the carrier can always arrange the route so they finish back at the start. Each time they enter an intersection, they can also leave it, so the streets pair up.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part finishes the proof that a graph with an Euler tour must have one, then starts directed graphs and shows how adjacency matrices count walks.

Key ideas

The proof of the Euler tour theorem ends by contradiction. If the longest walk missed an edge touching the walk, you could extend the walk to be longer, which is impossible, so the walk must use every edge and be an Euler tour. 22:27
In a directed graph, every edge has a direction, like a one-way street. An edge from V2 to V3 is a different edge from one going from V3 to V2. 24:04
Because edges have direction, a vertex has two kinds of degree: indegree counts edges coming in, and outdegree counts edges going out. 24:49
An adjacency matrix is a grid where entry aij is 1 if there is an edge from Vi to Vj, and 0 if there is not. 26:46
Raising the adjacency matrix to the power k gives a table of how many directed walks of length k go from each vertex to each other vertex. 27:47

Words to know

Euler tour: A walk through a graph that uses every edge exactly once and ends where it started.
Directed graph: A graph where each edge is a one-way connection, shown with an arrow.
Indegree: The number of edges pointing into a vertex in a directed graph.
Adjacency matrix: A grid of 1s and 0s that records which vertices are directly connected, with the direction of each connection.

Example

Think of a city with one-way streets. Each street is an edge with a direction. Counting how many streets lead into an intersection is like finding its indegree, and counting how many lead out is like finding its outdegree. An adjacency matrix is a table that records, for every pair of intersections, whether a one-way street runs directly between them.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part shows why raising a graph's adjacency matrix to a power counts the walks of that length between points, and proves it using induction.

Key ideas

A walk is a route that follows edges from one point to another. The lesson says the entries of the adjacency matrix raised to a power, such as the cube, count how many walks of that length go between two points. 30:00
The proof uses induction, a method that checks a starting case and then shows that if the rule works for some number k, it also works for k plus 1. 31:06
The base case is k equals 1. A walk of length 1 exists only if there is a direct edge, and the adjacency matrix records exactly that, so the two agree. 33:03
For the induction step, any walk of length k plus 1 can be split into a walk of length k to some point h, followed by one edge from h to the end. Summing over all such h gives the count, and matrix multiplication turns that sum into the matrix for power k plus 1. 36:20
The lesson then moves on to directed graphs, where edges have a direction, and to tournament graphs, a special kind of directed graph. 39:04

Words to know

adjacency matrix: A grid of numbers that records which points in a graph are joined by an edge. An entry is 1 if there is an edge and 0 if there is not.
walk: A route that moves from one point to another by following edges, one step at a time, where steps can repeat points or edges.
induction: A proof method. You check that the rule works for the first case, then show that if it works for some case, it must also work for the next one.
matrix multiplication: A way of combining two grids of numbers by multiplying and adding entries in a set pattern. Here it is used to turn a power k matrix times the adjacency matrix into the power k plus 1 matrix.

Example

Imagine a map of bus routes between towns, where each direct bus link is an edge. If you want to know how many ways you can get from town A to town B using exactly three bus rides, you count every route that takes three steps and ends in town B. The matrix power does this counting for you all at once.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part explains what it means for a directed graph to be connected, introduces directed acyclic graphs (DAGs) and tournament graphs, and sets up a goal of finding a path that visits every vertex once.

Key ideas

In a directed graph, edges have arrows, so being connected is stricter. A directed graph is strongly connected if you can follow arrows from any vertex to any other vertex. 41:09
A directed acyclic graph (DAG) is a directed graph with no directed cycles, meaning you can never follow the arrows and return to where you started. DAGs are used in scheduling and optimization. 44:09
A tournament graph models a competition where every pair of teams plays once. Each game is one directed edge pointing from the winner to the loser. 46:44
In a tournament there is often no single clear best team, so the lecture asks whether you can always find a path that visits every team exactly once. Such a path is called a Hamiltonian path. 49:28

Words to know

strongly connected: A directed graph where, for every pair of vertices, you can follow the arrows from one to the other.
directed acyclic graph (DAG): A directed graph with arrows but no loop of arrows that brings you back to where you started.
tournament graph: A graph where every pair of vertices is joined by exactly one arrow, showing which one wins the match.
Hamiltonian path: A walk through a graph that visits every vertex exactly once.

Example

Think of a sports league where every team plays every other team once and the winner of each game is recorded as an arrow. You could try to line up all the teams so that each one beats the next one in the line, which is like finding a path that visits every team once. The lecture says this kind of path can always be found in a tournament graph.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–1:00:00

This part starts a proof that every tournament graph, where every pair of nodes has exactly one arrow between them, contains a directed Hamiltonian path that visits every node exactly once.

Key ideas

The goal is to prove that every tournament graph has a directed Hamiltonian path, which is a walk along the arrows that visits every vertex exactly once. 50:26
The proof uses induction on the number of nodes. The base case is one node, which is trivially a path because a single vertex has no edges to worry about. 53:06
For the inductive step, take a tournament graph with n plus 1 nodes and remove one node. What is left is still a tournament graph on n nodes, so the induction hypothesis gives us a directed Hamiltonian path through those n nodes. 58:15
The remaining job is to add the removed node back into that path so that a new path covers all n plus 1 nodes. The lesson stops before showing how to do this. 59:40

Words to know

directed Hamiltonian path: A route that follows the direction of the arrows, goes from one node to the next, and visits every node exactly once.
induction: A proof method: show the claim holds for the smallest case, then show that if it holds for a size n, it also holds for size n plus 1.
induction hypothesis: The statement you assume is true for some size n, so you can use it to prove the statement for the next size up.
base case: The smallest case, which you check directly to get the induction started.

Example

Imagine a small school where every pair of students plays one game against each other, and each game has a winner. Can you line up all the students so that each one beats the next person in the line? The theorem says you always can, and the proof builds that line one student at a time.

3 checked practice questions for this part are in the app.

Part 7 · 1:00:00–1:10:00

This part shows how to fit one extra player into a line of players in a tournament, where every player beats some and loses to others, so that each player appears exactly once.

Key ideas

A tournament graph is a set of points where every pair of points has exactly one arrow between them, so one of the two always beats the other. This rule is what the proof depends on. 1:03:00
Some easy cases are already solved. If the extra vertex V points to the first vertex in the line, you can just put V at the front of the path. 1:00:43
The hard case is when V is pointed to from the start of the line. The fix is to find the first spot in the line where V beats the vertex there, then place V just before it. 1:04:58
Why does that spot work? If the vertex just before it did not beat V, then V would beat it, which breaks the rule that we picked the first such spot. So the vertex before must beat V, and V fits in between. 1:07:07
The lesson says you can also pick the last spot where the vertex beats V, using a symmetrical argument. It then starts a chicken game, but this part ends before it explains that game. 1:08:36

Words to know

tournament graph: A set of points where every pair is joined by exactly one arrow, so one always beats the other, like a round-robin where every team plays every other team once.
Hamiltonian path: A route that visits every point exactly once, with no point skipped and none visited twice.
directed edge: A one-way connection drawn as an arrow from one point to another, so it only goes one way.
contradiction: A result that cannot be true because it breaks something we already know, which shows our starting guess was wrong.

Example

Think of a line of runners in a race where every pair of runners has a clear winner in a head-to-head match. If you want to add a new runner and keep the line in order, you find the first runner in the line that the new one beats and step in just before them. Everyone else stays in order and nobody is left out.

3 checked practice questions for this part are in the app.

Part 8 · 1:10:00–1:22:45

This part explains what a king chicken is in a pecking-order graph and proves that the chicken with the most outgoing pecks is always a king.

Key ideas

A chicken U virtually pecks chicken V if U pecks V directly, or if U pecks some other chicken W who pecks V. Virtual pecking can go through one helper. 1:10:14
A king chicken is one that virtually pecks every other chicken in the group. 1:12:07
A tournament graph can have more than one king. In the four-chicken example, three chickens were kings. 1:13:37
The chicken with the highest outdegree, meaning the most outgoing pecks, is always a king. 1:16:09
The proof works by contradiction: assume the top chicken U is not a king, then find a chicken V with more outgoing pecks than U. That breaks the assumption that U has the most, so U must be a king. 1:22:04

Words to know

virtually peck: To peck someone indirectly, either directly or through one helper who pecks them for you.
tournament graph: A group where every pair of chickens has exactly one arrow showing who pecks whom.
outdegree: The number of arrows leaving a chicken, which here means how many chickens it pecks directly.
proof by contradiction: Assume the opposite of what you want to show, then follow the logic until you reach something impossible. That shows the assumption was wrong.

Example

Picture a group of friends where each person can either ask someone directly or ask a friend to ask for them. The friend who has the most people they can ask directly is also the one who can get the most people to do something, either alone or through a helper. In the lesson, the chicken with the most outgoing pecks is always able to reach everyone in that indirect way.

3 checked practice questions for this part are in the app.

← Lecture 6: Graph Theory and Coloring · Lecture 11: Relations, Partial Orders, and Scheduling →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York