ArticleslgStudy

mathematics

Graham–Pollak theorem

Graham–Pollak theorem is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Graham–Pollak theorem rather than just read about it. In short: In graph theory, the Graham–Pollak theorem states that the edges of an n {\displaystyle n} -vertex complete graph cannot be partitioned into fewer than n − 1 {\displaystyle n-1} complete bipartite graphs. It was first published by Ronald Graham and Henry O.

Graham–Pollak theorem — main illustration
Graham–Pollak theorem — illustration

Key takeaways

  • Graham–Pollak theorem belongs to mathematics; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect Graham–Pollak theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of Graham–Pollak theorem from memory before moving on to harder problems.

Reference excerpt

In graph theory, the Graham–Pollak theorem states that the edges of an n {\displaystyle n} -vertex complete graph cannot be partitioned into fewer than n − 1 {\displaystyle n-1} complete bipartite graphs. It was first published by Ronald Graham and Henry O. Pollak in two papers in 1971 and 1972 (crediting Hans Witsenhausen for a key lemma), in connection with an application to telephone switching circuitry. The theorem has since become well known and repeatedly studied and generalized in graph theory, in part because of its elegant proof using techniques from algebraic graph theory. More strongly, Aigner & Ziegler (2018) write that all proofs are somehow based on linear algebra: "no combinatorial proof for this result is known".

Construction of an optimal partition A partition into exactly n − 1 {\displaystyle n-1} complete bipartite graphs is easy to obtain: just order the vertices, and for each vertex except the last, form a star connecting it to all later vertices in the ordering. Other partitions are also possible.

Proof of optimality The proof of the Graham–Pollak theorem described by Aigner & Ziegler (2018) (following Tverberg 1982) defines a real variable x i {\displaystyle x_{i}} for each vertex v i ∈ V {\displaystyle v_{i}\in V} , where V {\displaystyle V} denotes the set of all vertices in the graph. Let the left sides and right sides of the k {\displaystyle k} th bipartite graph be denoted L k {\displaystyle L_{k}} and R k {\displaystyle R_{k}} , respectively and for any set S {\displaystyle S} of vertices define X ( S ) {\displaystyle X(S)} to be the sum of variables for vertices in S {\displaystyle S} :

X ( S ) = ∑ v i ∈ S x i . {\displaystyle X(S)=\sum _{v_{i}\in S}x_{i}.}

Then, in terms of this notation, the fact that the bipartite graphs partition the edges of the complete graph can be expressed as the equation

∑ i < j x i x j = ∑ k X ( L k ) X ( R k ) . {\displaystyle \sum _{i<j}x_{i}x_{j}=\sum _{k}X(L_{k})X(R_{k}).}

Now consider the system of linear equations that sets X ( V ) = 0 {\displaystyle X(V)=0} and X ( L k ) = 0 {\displaystyle X(L_{k})=0} for each k {\displaystyle k} . Any solution to this system of equations would also obey the nonlinear equations

… excerpt ends here. Continue reading the full article.

Illustrations

Graham–Pollak theorem: Partition of the edges of the complete graph K 6 {\displaystyle K_{6}} into five complete bipartite subgraphs: K 2 , 2 {\displaystyle K_{2,2}} (light red), K 2 , 3 {\displaystyle K_{2,3}} (light blue), K 1 , 3 {\displaystyle K_{1,3}} (yellow), and two copies of K 1 , 1 {\displaystyle K_{1,1}} (dark red and dark blue). According to the Graham–Pollak theorem, a partition into fewer than five complete bipartite subgraphs is not possible.
Partition of the edges of the complete graph K 6 {\displaystyle K_{6}} into five complete bipartite subgraphs: K 2 , 2 {\displaystyle K_{2,2}} (light red), K 2 , 3 {\displaystyle K_{2,3}} (light blue), K 1 , 3 {\displaystyle K_{1,3}} (yellow), and two copies of K 1 , 1 {\displaystyle K_{1,1}} (dark red and dark blue). According to the Graham–Pollak theorem, a partition into fewer than five complete bipartite subgraphs is not possible.

Worked examples

Example 1 — a first encounter with Graham–Pollak theorem

Start with the simplest possible case. Write down what Graham–Pollak theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Graham–Pollak theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Graham–Pollak theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Graham–Pollak theorem

In research
Graham–Pollak theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses Graham–Pollak theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
Graham–Pollak theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Algebraic graph theory, Theorems in graph theory, so understanding it makes those chapters shorter.
In everyday life
Look for Graham–Pollak theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.
Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Graham–Pollak theorem” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Graham–Pollak theorem in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what Graham–Pollak theorem means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain Graham–Pollak theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Graham–Pollak theorem in simple terms?

In graph theory, the Graham–Pollak theorem states that the edges of an n {\displaystyle n} -vertex complete graph cannot be partitioned into fewer than n − 1 {\displaystyle n-1} complete bipartite graphs. It was first published by Ronald Graham and Henry O.

Why does Graham–Pollak theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Graham–Pollak theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Graham–Pollak theorem.

Tags

  • Algebraic graph theory
  • Theorems in graph theory

Keep exploring