Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2010/iii/paper-12/4/ii/solution
Past exam of the mathematics course of the University of Cambridge 2010 iii Paper 12 4 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Write , an integer under the stated divisibility assumption. The degree relation gives . Take the disjoint union of graphs of copies of the complete bipartite graph , placing its -vertex part in and its -vertex part in . The total part sizes are then and . Each left vertex has vertex degree , and each right vertex has vertex degree , so the graph has exactly the required biregular graph parameters.
An independent set in one component can be any subset of its left part or any subset of its right part. It cannot contain a vertex from both parts, because all cross-pairs are edges. The two families share only the empty set, so the component has independent sets. Choices in different connected components of a graph are independent combinatorial choices, and their counts multiply. HenceThis attains equality in part (i). It also explains the entropy weight there: the empty selected left neighbourhood permits all subsets of the opposite part.
New to topics? Read the docs here!