A graph G has n + k points. A is a subset of n points and B is the subset of the other k points. Each point of A is joined to at least k - m points of B where nm < k. Show that there is a point in B which is joined every point in A.
Solution
This is just the pigeonhole principle. There are at least n(k-m) > (n-1)k edges from points of A to points of B and there are k points in B. So some point of B must have at least n edges (otherwise there would be ≤ (n-1)k edges). That point is joined to every point of A.
© John Scholes
jscholes@kalva.demon.co.uk
7 March 2004
Last corrected/updated 7 Mar 04