15th Irish 2002 Problem A2 A graph has n points. Each point has degree at most 3. If there is no edge between two points, then there is a third point joined to them both. What is the maximum possible value of n? What is the maximum if the graph contains a triangle?
10, 8 Solution Take any point A. A is joined to at most three points, call them B, C, D. Any other point X must be joined to one of B, C, D. Each of B, C, D is joined to at most two other points. So there are at most 1 + 3 + 3·2 = 10 points in all. 10 points are possible. Take points A, B, C, D, E, F, G, H, I, J and edges AB, AC, AD, BE, BF, CG, CH, DI, DJ, EH, EJ, FG, FI, GJ, HI. It is easy to check that every point has degree 3. Now take any two points not joined by an edge. For A,E or A,F both are joined to B. Similarly, both A,G and A,H are joined to C, and both A,I and A,J are joined to D. Both B,C and B,D are joined to A. B,G and B,I are joined to F. B,H and B,J are joined to E. Similarly, C,D are joined to A. C,E and C,I are joined to H. C,F and C,J are joined to G. Similarly, D,F and D,H are joined to I. D,E and D,G are joined to J. E,F are joined to B. E,G are joined to J. E,I are joined to H. F,H are joined to I. F,J are joined to G. G, I are joined to F. H, J are joined to E. If there is a triangle ABC. Then there is at most one other point D joined to A. Now any other point must be joined to B, C, or D (so that it and A are both joined to a common point). There is at most one other point E joined to B, and at most one other point F joined to C. There are at most two other points G, H joined to D. So we get at most 8 points in all. 8 points is possible. Take edges AB, AC, AD, BC, BE, CF, DG, DH, EG, EH, FG, FH. Every point has degree 3. We have A,E joined to B; A,F joined to C; A,G joined to D; A,H joined to D; B,D joined to A; B,F joined to C; B,G joined to E; B,H joined to E; C,D joined to A; C,E joined to B; C,G joined to F; C,H joined to F; D,E joined to G; D,F joined to G; E,F joined to G; G,H joined to D. 15th Irish 2002 © John Scholes jscholes@kalva.demon.co.uk 8 January 2004 Last updated/corrected 8 Jan 04