{"id":"palomar/PALOMAR-2026-10-23-000006","url":"https://github.com/jtraverso/graham-pollak/tree/68d32f0faf102fc1716ac89ffc861eefe897e749","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-10-23-000006-v1.json","repo":"https://github.com/jtraverso/graham-pollak","tags":["math.CO","msc:05C70","msc:05C50","graph-theory","biclique-partitions","formalization"],"score":0,"title":"The Graham–Pollak theorem","trust":"high","domain":"math.CO","source":"palomar","authors":["Juan Pablo Traverso Gianini"],"reviews":0,"subject":"math.CO","summary":"A Lean 4 / Mathlib formalization of the Graham–Pollak theorem: the edge set of the complete graph K_n cannot be partitioned into fewer than n − 1 complete bipartite graphs, together with the matching construction by n − 1 stars. Biclique decompositions are encoded by families of pairs of disjoint vertex sets covering every pair of distinct vertices exactly once. Mathlib does not contain this theorem.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-10-23","reactions":{},"formalized":true,"formalizes":[{"title":"On the addressing problem for loop switching","identifier":"doi:10.1002/j.1538-7305.1971.tb02618.x","relationship":"formalizes"}]}