Graph-Theoretic Methods

In one sentence

Draw the objects as vertices and “are related” as edges, and the problem becomes a graph. The simplest theorem of graph theory:

v \sum de g v = 2 \times (number of edges)

(Each edge joins two vertices and is counted twice: this is “counting in two ways” on a graph.) So the number of vertices of odd degree is always even. Add coloring the edges (know / do not know) and triangles, and many problems of the form “any $n$ people…” get an intuitive model.

Predict first

Can each of $9$ people have shaken hands with exactly $3$ of the others?

YesNo

Choose an answer first; then you can see the result.

Example: among any 6 people, there are 3 who all know each other or 3 who all do not (the classic Ramsey problem)

Step 1 / 5

The model
People → vertices; two people who know each other → a red edge, who do not → a blue edge. To prove: every two-coloring of the complete graph $K_{6}$ on $6$ vertices has a monochromatic triangle.

$know = red, do not know = blue$
5 people are not enough
Look at one vertex
Look at those three people
Otherwise all are blue

Stop 1 · Families of subsets: the intersection graph (Vol. 1)

In a family of sets, “two sets intersect” is a pairwise relation. Draw the sets as vertices, and the handshake lemma can answer existence questions.

Example: are there 7 sets such that each one intersects exactly 3 of the others?

Step 1 / 3

Draw a graph
Each set is a vertex, and two intersecting sets are joined by an edge. The condition becomes: $7$ vertices, each of degree $3$ .

$de g A_{i} = 3 (i = 1, \dots, 7)$
The handshake lemma
Contradiction

Stop 2 · Partitions of a set: bipartite graphs and odd cycles (Vol. 1)

Split the vertices into two groups so that every edge goes across: that is a bipartite graph. Whether it can be done depends on whether there is an odd cycle.

7

people sit in a circle, and each one does not get along with the two neighbors (an edge). You want to put them in two rooms so that people who do not get along are in different rooms. Try labeling A, B alternately around the circle on paper: what happens when you come back around?

Label the groups alternately A, B, A, B… around the cycle. After $7$ steps you are back at the start, which should now be B, but it is A. So an odd cycle cannot be split into two groups. Conversely, one can prove that a graph with no odd cycle can always be split into two groups (start from any vertex and group the vertices by the parity of their distance).

Stop 3 · Combinatorial estimates: graphs without triangles (Vol. 6)

6

vertices,

9

edges, no triangle. What happens if you add any one more edge?

One problem, several solutions

A graph on $n$ vertices has no triangle. Prove that the number of edges satisfies $e \leq \frac{n ^{2}}{4}$ (Mantel's theorem).

Counting in two ways + Cauchy

For each edge $uv$ : $u$ and $v$ have no common neighbor (otherwise there would be a triangle), so $de g u + de g v \leq n$ . Sum over all edges; each vertex $v$ appears once in each of its $de g v$ edges, so $\sum_{v} (de g v)^{2} \leq n e$ . By the Cauchy inequality, $\sum (de g v)^{2} \geq \frac{( \sum de g v ) ^{2}}{n} = \frac{4 e ^{2}}{n}$ . So $\frac{4 e ^{2}}{n} \leq n e$ , that is, $e \leq \frac{n ^{2}}{4}$ .

CostA clear line of thought, using the Cauchy inequality from Vol. 6.

The extremal principle

Take a vertex $v$ of largest degree, $de g v = d$ . The $d$ neighbors of $v$ are pairwise non-adjacent, so every edge has at least one end among the other $n - d$ vertices, each of degree $\leq d$ : $e \leq d (n - d) \leq \frac{n ^{2}}{4}$ .

CostNo inequality needed, but you have to think of taking the vertex of largest degree.

Equality is reached by the complete bipartite graph: two groups of $\frac{n}{2}$ vertices each, all edges between the groups and none inside them. The graph above is the case $n = 6$ , with $9 = \frac{36}{4}$ .

Practice

Exercise 1Basic

At a party of $10$ people, each person shakes hands with exactly $3$ of the others. How many handshakes are there in all?

Exercise 2Basic

A graph on $10$ vertices has no triangle. At most how many edges can it have?

Exercise 3Advanced

Color every edge of the complete graph $K_{n}$ red or blue. What is the smallest $n$ for which there is a monochromatic triangle however the edges are colored?

Exercise 4Challenge

The edges of $K_{6}$ are colored red and blue in any way. What is the least possible number of monochromatic triangles?

In one sentence

Example: among any 6 people, there are 3 who all know each other or 3 who all do not (the classic Ramsey problem)

Stop 1 · Families of subsets: the intersection graph (Vol. 1)

Example: are there 7 sets such that each one intersects exactly 3 of the others?

Stop 2 · Partitions of a set: bipartite graphs and odd cycles (Vol. 1)

Stop 3 · Combinatorial estimates: graphs without triangles (Vol. 6)

Counting in two ways + Cauchy

The extremal principle

Practice

Mistake Museum · Exhibits from this stop

Counting each handshake only once

Thinking that 5 people cannot avoid it either

Stops on this line