Graphs and Their Models

The question

A registrar schedules final exams for six courses: Algebra, Biology, Chemistry, Drama, Economics and French. Two exams cannot share a time slot if some student takes both courses. Here are the students' course lists:

The registrar does not care who the students are, only which pairs of courses conflict. Draw a point for each course and a line between two courses whenever some student takes both:

That picture is a graph, and everything the registrar needs is in it: which exams may share a slot, and which may not. This module sets up the language: what a graph is, the families of graphs that come up again and again, and how to count their edges with proofs rather than pictures.

The naive approach, and where it wastes work

The direct way to build the conflict graph checks every pair of courses against every student:

from itertools import combinations

students = {"Ana": "ABC", "Ben": "CD", "Caro": "DEF", "Dev": "AF"}
courses = sorted(set("".join(students.values())))

def conflicts_by_pairs(students, courses):
    return {(a, b) for a, b in combinations(courses, 2)
            if any(a in taken and b in taken for taken in students.values())}

edges = conflicts_by_pairs(students, courses)
assert len(edges) == 8 and ("A", "F") in edges and ("B", "D") not in edges

With $c$ courses and $s$ students, that is $\left(\genfrac{}{}{0ex}{}{c}{2}\right)·s$ checks: for a university with 3,000 courses and 30,000 students, over ${10}^{11}$. Almost every check finds nothing, because each student takes only a few courses.

One student at a time

A student's list already says which conflicts that student creates: every pair of courses on it. So instead of asking, for each pair of courses, whether some student takes both, go through the students once and add each student's pairs.

Before any student there are no edges, and each student adds exactly their own pairs, so the statement stays true from one panel to the next. After the last student it says that the picture is the conflict graph. Ana's three courses make 3 pairs, Ben's two make 1, Caro's make 3 and Dev's make 1: eight pairs visited, against the $\left(\genfrac{}{}{0ex}{}{62}{·}\right)4=60$ checks of the first method.

from math import comb

visits = sum(comb(len(taken), 2) for taken in students.values())
assert visits == 8 and comb(len(courses), 2) * len(students) == 60

The lab asks you to write this construction for a different school.

What a graph is

A graph $G$ consists of a set $V(G)$ of vertices and a set $E(G)$ of edges; each edge has two endpoints. An edge with both endpoints equal is a loop, and two edges with the same pair of endpoints are multiple edges. A simple graph has neither, and then an edge is just an unordered pair $uv$ of distinct vertices. In this course a graph is simple unless we say otherwise.

Some models need the general version. In 1736 Euler studied the seven bridges of Königsberg, which join four land masses: two land masses joined by two bridges need two edges between the same pair of vertices. Module 4 answers his question.

Vocabulary used from here on:

• $u$ and $v$ are adjacent, or neighbors, when $uv$ is an edge; the edge is incident to $u$ and $v$. The neighborhood $N(v)$ is the set of neighbors of $v$.
• A path is a list of distinct vertices, each adjacent to the next. A graph is connected if every two vertices are joined by a path. (Module 3 makes this precise and proves the basic facts.)

In Python the course stores a graph as a dict from each vertex to the set of its neighbors:

def network(edges):
    g = {}
    for u, v in edges:
        g.setdefault(u, set()).add(v)
        g.setdefault(v, set()).add(u)
    return g

conflict = network(edges)
assert conflict["D"] == {"C", "E", "F"}

Families that come up again and again

• The path $P_n$: vertices $v_1,\dots ,v_n$, edges $v_i{v}_{i+1}$. It has $n-1$ edges.
• The cycle $C_n$ ($n\ge 3$): the path plus the edge $v_n{v}_1$. It has $n$ edges.
• The complete graph $K_n$: $n$ vertices, every two adjacent.
• A graph is bipartite if its vertices split into two sets $X$ and $Y$, its parts, so that every edge has one endpoint in each. The complete bipartite graph $K_{r,s}$ has parts of sizes $r$ and $s$ and every possible edge between them.

Not every graph is bipartite. However the three vertices of $K_3$ are split into two sets, two of them land in the same set (pigeonhole), and those two are adjacent. So $K_3$ is not bipartite.

Proposition. $K_n$ has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=n(n-1)/2$ edges, and $K_{r,s}$ has $rs$ edges.

Proof. In $K_n$ every pair of distinct vertices is an edge, and every edge is such a pair: the map from edges to their sets of endpoints is a bijection onto the 2-element subsets of $V(K_n)$, and there are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ of those.

In $K_{r,s}$ every edge has exactly one endpoint in $X$ and one in $Y$, and every such pair is an edge. So the map sending an edge to its ordered pair (endpoint in $X$, endpoint in $Y$) is a bijection onto $X\times Y$, which has $rs$ elements. $◻$

Proof move used here. Bijection: count a set by matching it, one to one and onto, with a set you can already count. Read the definitions exactly: "every pair is an edge" gives onto, and "edges are pairs of distinct vertices" (the graph is simple) gives one to one.

In the conflict graph, Ana takes three courses, so she alone creates $\left(\genfrac{}{}{0ex}{}{32}{=}\right)3$ conflicts: a copy of $K_3$.

Complements

The complement $\bar{G}$ of a simple graph $G$ has the same vertices, and $uv$ is an edge of $\bar{G}$ exactly when it is not an edge of $G$. For the registrar, the complement of the conflict graph shows which exams may share a slot.

Proposition. If $G$ has $n$ vertices, then $e(G)+e(\bar{G})=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$.

Proof. Each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs of distinct vertices is an edge of exactly one of $G$ and $\bar{G}$, so the two edge sets split the pairs between them. $◻$

For the four students, $e(G)=8$ and $\left(\genfrac{}{}{0ex}{}{62}{=}\right)15$, so seven pairs of exams may share a slot.

Proof move used here. Decomposition: split the pairs into two classes, each pair in exactly one, and the two counts add up to the total.

Subgraphs and induced subgraphs

A subgraph of $G$ is a graph $H$ with $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$. For a set $S$ of vertices, the induced subgraph $G[S]$ keeps the vertices of $S$ and every edge of $G$ with both endpoints in $S$.

In the conflict graph, the courses $A,B,C$ induce a triangle, because all three pairs conflict. The path $B,A,C$ (edges $BA$ and $AC$) is a subgraph of the conflict graph, but not an induced one: keeping the vertices $B$ and $C$ forces you to keep the edge $BC$.

Two phrases that proofs turn on

Statements in this course lean on two phrases, and each one tells you what a proof owes.

"Exactly when" (also written "if and only if") makes two claims, and a proof owes both. Take the statement: a simple graph with $n$ vertices has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges exactly when it is complete. One direction is the proposition about $K_n$. For the other, suppose $G$ has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges. Then $e(\bar{G})=\left(\genfrac{}{}{0ex}{}{n}{2}\right)-e(G)=0$ by the complement count, so no pair of vertices is a non-edge of $G$, and $G$ is complete. Proving only one direction proves a weaker statement.

"Every" makes a claim about all objects of some kind, and a single counterexample refutes it: an object that meets every hypothesis of the claim and still fails its conclusion. "Every subgraph of a complete graph is complete" is refuted by the path $B,A,C$ inside the triangle on $A,B,C$ from the last section. An object that misses a hypothesis refutes nothing, so check the hypotheses first.

What a certificate costs

Even at this level, claims about graphs come with evidence. "These two exams conflict" is proved by naming one student who takes both; "these two exams do not conflict" needs everyone's list. "$G$ is bipartite" is proved by showing the parts $X$ and $Y$, checked in one pass over the edges. The lab asks for evidence of this kind both ways.

A problem that looks different

A park ranger wants a hiking loop that starts and ends at the visitor center and walks every trail exactly once. Before marking any route on the map, she would like to know whether such a loop can exist at all, and what would prove that it cannot. Nothing in the question says "graph". Module 4 answers it; the lab's last exercise is another question of this kind.

Practise

The lab runs in your browser. Your code builds the conflict graph of another school one student at a time, drawing each step, and decides whether a piece of a graph is an induced subgraph, naming the vertex or edge that proves it either way. Half of the lab is proofs: assemble a proof about when the conflict count is as large as it can be, find the false step in an argument about bipartite graphs, and write a proof for a problem that names no technique.

Recap

• You can now: define simple graphs and multigraphs; use adjacency, neighborhoods, paths and connectedness; count the edges of $K_n$ and $K_{r,s}$ by bijections; prove the complement edge count; tell a subgraph from an induced subgraph; and say what an "exactly when" proof and a counterexample each owe.
• Invariant: after the first $k$ students, the graph has exactly the conflicts those students create. And each edge of a simple graph is exactly one pair of distinct vertices, so counting edges is counting pairs.
• Complexity achieved: a graph stored as a dict of neighbor sets answers "who are $v$'s neighbors?" in time proportional to their number; building the conflict graph one student at a time costs about the number of conflicts each student creates, not $\left(\genfrac{}{}{0ex}{}{c}{2}\right)·s$.
• Failure mode: forgetting that an induced subgraph must keep every edge among its vertices; and counting a pair of courses once per student instead of once.
• In real software: NetworkX stores graphs as dicts of neighbor dicts, and nx.complement, nx.complete_graph, nx.complete_bipartite_graph and G.subgraph(S) (which is induced) build the objects of this module.
• Next: module 2 asks when two drawings are the same graph.

Check yourself

After the lab, the tutor will ask you to defend your work out loud:

1. In the proof that $K_n$ has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges, where is it used that the graph is simple?
2. Why is the complement defined only for simple graphs?
3. Give a subgraph of the conflict graph on the courses $C,D,E,F$ that is not induced, and say which edge it is missing.

Topic list modeled on the public syllabus of UIUC Math 412 (Graph Theory), which follows D. B. West, Introduction to Graph Theory, 2nd ed., Chapters 1–7. All lessons, proofs, examples, code and exercises here are original. This course is independent and not affiliated with or endorsed by the University of Illinois.