Lecture notes · Math for Computer Science · Lecture 6

Graph Theory and Coloring

MIT 6.042J Mathematics for Computer Science, lecture 6, 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 graphs as dots joined by lines, explains why they matter in computer science, and begins a formal definition of a graph.

Key ideas

Graphs are useful structures in computer science. They appear in scheduling, communications, optimization, and the design and analysis of algorithms. 1:10
The lecturer says graph theory can help answer a question about who has more partners, even though the lecture's data-based answer is not part of this section. 8:16
Informally, a graph is just a bunch of dots connected by lines. The dots are called nodes, and the lines are called edges. 8:37
Nodes and sometimes edges can be given labels, such as x1 through x7, so each one can be named. 8:57
The formal definition says a graph G is a pair of sets, usually called V and E. V is the set of vertices (also called nodes), and it must not be empty. The lesson text stops before it says what E is. 9:17

Words to know

graph: A picture-like structure made of dots and the lines that join them. Graphs show how things connect.
node: One of the dots in a graph. It is also called a vertex.
edge: One of the lines in a graph that connects two nodes.
set: A collection of items grouped together. In the formal definition, V is a set of nodes.

Example

Think of a subway map. Each station is a dot, and each track between two stations is a line. The map is a graph, because it shows which stations connect to which, even though it leaves out distances and details.

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

Part 2 · 10:00–20:00

This part explains what a graph is (dots joined by lines), how nodes, edges, adjacency, and degree work, and how a graph can model opposite-gender partnerships.

Key ideas

A graph is a set of nodes (also called vertices) joined by edges. An edge is a pair of nodes, and the order does not matter, so x1 to x2 is the same edge as x2 to x1. 10:06
A graph must have at least one node, but it does not need any edges. A graph with three nodes and no edges is still a valid graph. 11:59
Two nodes are adjacent if an edge joins them. The degree of a node is the number of edges touching it. 12:48
To model partnerships, each person is a node and each opposite-gender partnership is an edge. Only edges between a man and a woman count. 16:32
The goal is to compare the average degree of the men with the average degree of the women. Degree here means the number of opposite-gender partners a person has. 19:26

Words to know

node (vertex): One of the dots in a graph. The lecture uses the two words to mean the same thing.
edge: A line between two nodes. It is a pair of nodes, and the order in the pair does not matter.
degree: The number of edges touching a node. In the partnership model, it is how many partners a person has.
adjacent: Two nodes are adjacent when an edge connects them directly.

Example

Think of a bus map. Each bus stop is a node, and each road that links two stops is an edge. The degree of a stop is how many roads connect to it. A stop with many roads has a high degree, and a stop with no roads has a degree of 0.

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

Part 3 · 20:00–30:00

This part shows how a simple graph count proves that men and women have almost the same average number of opposite-gender partners, and then shows how edges can stand for conflicts, as in exam scheduling.

Key ideas

The average degree of a group is the total of all their degrees divided by how many people are in the group. A degree is the number of edges (connections) touching one node. 21:34
Because every relationship links one man to one woman, adding up all the men's degrees counts each edge exactly once. So that total is just the number of edges. 22:20
Adding up the women's degrees also gives the number of edges. So both averages share the same top number, and when you divide one by the other, that number cancels out. 24:00
What is left is the number of women divided by the number of men, about 1.0325. So the average man has about 3% more partners, and this is caused by the counts of men and women, not by how people behave. 24:22
In a different use of graphs, an edge can mean the opposite of a friendship: two items that must not happen at the same time. For exams, an edge joins two classes that share students, so their exams cannot be in the same slot. 28:02

Words to know

degree: The number of connections (edges) that touch one node in a graph. For a person in this example, it is how many partners they have.
edge: A line connecting two nodes in a graph. Here it means a relationship between two people, or a conflict between two classes.
bipartite graph: A graph with two groups of nodes where every edge goes from one group to the other, like men linked only to women.
cardinality: A fancy word for the count of how many items are in a set. The cardinality of E is the number of edges.

Example

Imagine a dance where every dance pairs one man with one woman. If there are 10 men and 12 women, each dance uses the same number of pairings, so the men each dance with more partners on average than the women do. The total number of pairings is the same for both groups, so only the head count of each group changes the average.

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

Part 4 · 30:00–40:00

This part explains graph coloring, which is a way to schedule things so that conflicting items never share a slot, and why finding the best schedule is so hard.

Key ideas

Graph coloring means giving each node a color so that nodes joined by an edge get different colors. In the exam example, each color is a time slot, and two exams that share a student cannot share a slot. 30:42
The chromatic number is the smallest number of colors you need to color a graph this way. For the example graph, the answer is three, because a triangle of three connected nodes needs three different colors. 36:03
Checking that a coloring works is easy: you just look at each edge and confirm its two ends have different colors. Finding the best coloring from scratch is very hard, and no one knows a fast method for large graphs. 36:44
The three-coloring problem is NP-complete, a label for a large group of hard problems. If anyone found a fast way to solve one of them, all of them could be solved fast. 38:13
Even though these problems are hard in theory, people still have to solve them in practice. MIT still has to schedule its exams, so you have to find some workable answer. 39:38

Words to know

graph coloring: Giving each node in a network a label (a color) so that connected nodes never get the same label.
chromatic number: The fewest number of colors you need to color a graph correctly.
NP-complete: A group of thousands of hard problems where a proposed answer is quick to check, but finding the answer is not known to be quick.
adjacent: Next to each other, or connected by an edge in a graph.

Example

Think of the exam scheduling problem: each course is a node, and two courses are joined by an edge if some student takes both. You can check a finished schedule quickly by looking at each pair of linked courses, but finding the schedule that uses the fewest time slots can take a huge amount of trial and error. That gap between checking and finding is the core idea of this part.

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

Part 5 · 40:00–50:00

This part explains a simple, fast way to color a graph so that connected nodes get different colors, and why the order you visit the nodes matters.

Key ideas

The basic graph coloring algorithm puts the nodes in some order, then colors them one at a time. Each node gets the lowest color that does not clash with a neighbor that is already colored. 44:02
The order you visit the nodes changes how many colors you end up using. The same graph can take four colors with one order and three with another. 45:35
Visiting the nodes with the largest degree first usually works well. A node's degree is the number of connections it has to other nodes. 47:05
This method is a greedy algorithm: it makes the best choice at each step and never goes back to fix earlier choices. It is fast, but it does not always give the best answer. 48:52
If every node has degree at most d, this method never needs more than d + 1 colors. The lesson says it will prove this. 49:58

Words to know

degree: The number of connections a node has to other nodes in the graph.
greedy algorithm: A method that takes the best option available at each step, one after another, and never goes back to change earlier choices.
legal color: A color that a node can take without matching the color of any neighbor it is connected to.
neighbor: A node that is directly connected to another node by an edge.

Example

Imagine giving each guest at a party a sticker color, where any two guests who know each other must have different colors. You go through the guests one at a time and give each one the first color that no friend already has. If you seat the most social guests first, you often finish with fewer colors in total.

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

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

This part proves that a simple coloring method never needs more than one color beyond the largest number of connections any node has, using induction on the number of nodes.

Key ideas

The basic coloring method uses at most d plus 1 colors, where d is the largest degree (number of connections) of any node, no matter what order the nodes are taken in. 50:00
If every node has at most three connections, the method needs at most four colors, even for a graph with 1,000 nodes. That makes the rule very useful for big graphs. 50:40
For graph proofs, the usual first try is to do induction on the number of nodes, n. Inducting on the largest degree d caused a mess on a real test. 53:51
The base case is a graph with one node. It has no edges, so one color is enough, and that equals d plus 1. 55:25
In the inductive step, remove the last node in the order to get a smaller graph. Removing a node can only lower degrees, never raise them, so the smaller graph still fits the induction hypothesis. 59:18

Words to know

degree: The number of edges (lines) that touch one node. In a graph where each node has degree at most 3, no node has more than 3 connections.
induction hypothesis: The statement you assume is true for a smaller case, so you can use it to prove the statement for the next, bigger case.
base case: The simplest case, which you check directly to show the statement works at the start. The rest of the proof builds on it.
inductive step: The part of the proof where you show that if the statement holds for a smaller case, it also holds for the next bigger case.

Example

Imagine a group of friends where each person knows at most three others. You want to give each person a team color so that no two friends share a color. The lesson's rule says you will never need more than four colors, no matter who you start with, which is the same idea as the d plus 1 rule.

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

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

This part shows that a simple coloring method never needs more than one more color than the largest number of neighbors any node has, and it explains why that limit is sometimes far too high.

Key ideas

If every node has at most d neighbors, the basic coloring method never needs more than d plus 1 colors. Here d is the degree, meaning the number of nodes a node is directly connected to. 1:00:00
The proof works by induction, which means you show the claim holds for a small case and then show that adding one more node keeps it true. The new node has at most d neighbors, so those neighbors block at most d colors, which leaves one of the d plus 1 colors free. 1:01:25
A complete graph, where every node is connected to every other node, needs exactly d plus 1 colors. So the bound cannot be made any smaller in general. 1:04:36
One example can show that a bound is the best possible, but it does not prove the bound holds for all graphs. A proof has to cover every graph. 1:06:23
Some graphs need far fewer colors than the bound allows. A two-sided graph and a star graph both have large degree but need only two colors, and the basic method also uses only two colors on the star graph. 1:08:36

Words to know

degree: The number of connections a node has. It is how many other nodes it is directly connected to.
chromatic number: The smallest number of colors you need to color every node so that no two connected nodes share a color.
clique: A group where every member is connected to every other member. In a graph, a clique is a set of nodes that all touch each other.
induction: A proof method. You show a claim is true for a starting case, then show that if it is true for one more step, it is true for the next step too.

Example

Think of a group of friends at a party where each pair who are talking to each other must wear different colored name tags. A person who talks to at most d others only has to avoid d tag colors, so with d plus 1 colors there is always one tag left for them. This is the same idea as the coloring method in the lesson.

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

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

This part shows that the simple coloring method can be very good or very bad depending on the order you pick the nodes, and it explains bipartite graphs and where coloring shows up in real problems.

Key ideas

The theorem gives an upper bound: a graph never needs more than d plus 1 colors, where d is the most edges any one node has. The simple algorithm often does much better than this bound. 1:10:00
The simple algorithm is not always good. On some graphs it can use far more colors than needed. 1:10:19
The order you visit the nodes in matters a lot. With one order, a complete bipartite graph with n nodes can need n over 2 colors, while a better order needs only two. 1:15:47
A bipartite graph is one whose nodes can be split into two sets, with every edge going from one set to the other. Such a graph can always be colored with two colors. 1:16:09
Coloring problems appear in real work. Akamai uses coloring to schedule software updates on servers so that paired servers are not updated at the same time, and the colors become waves of installs. 1:18:04

Words to know

bipartite: A graph whose nodes can be split into two groups, where every edge connects a node in one group to a node in the other group.
edge: A line that joins two nodes and shows they are linked, for example two countries that share a border or two servers that cannot be updated together.
upper bound: A limit that the true answer can never go above. It is a ceiling, not always the exact answer.
node: A single dot in a graph. It stands for one item, such as a person, a server, a country, or a radio tower.

Example

Think of seating guests at tables where some guests cannot sit together. If you seat people in a bad order, you may need many tables, but if you seat the guests in a smart order, you may need only a few. The order you use changes the number of tables you need, just as the order of nodes changes the number of colors the simple algorithm uses.

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

← Lecture 2: Induction · Lecture 10: Graph Theory III →

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