24th ASU 1990 Problem 3 A graph has 30 points and each point has 6 edges. Find the total number of triples such that each pair of points is joined or each pair of points is not joined.
1990 Solution There are 30·29·28/6 = 4060 triples in all. Let m be the number of triples with 0 or 3 edges, and let n be the number of triples with 1 or 2 edges. So m + n = 4060. Each point is joined to 6 others, so it is in 6·5/2 = 15 triples where it is joined to both the other points, and it is in 23·22/2 = 253 triples where it is not joined to either of the other points. So the total number of triples (a,b,c), where a is joined to b and c or not joined to b or c is 30(15+253) = 8040. This counts the m triples 3 times each, and the n triples once each, so 3m+n = 8040. Hence m = 1990. 24th ASU 1990 © John Scholes jscholes@kalva.demon.co.uk 2 March 2004 Last corrected/updated 2 Mar 04