11th Balkan 1994 Problem 4 Find the smallest n > 4 for which we can find a graph on n points with no triangles and such that for every two unjoined points we can find just two points joined to both of them. Solution
: n = 16. Let X be one of the points. Suppose it has degree m, so that it is joined to A 1 , A 2 , ... , A m . So no A i , A j can be joined (or we would have a triangle XA i A j ). If m = 1, then there cannot be any other points, for suppose Y is another point. Then Y is not joined to X, so there must be two points joined to X and Y, but there is only one point joined to X. Contradiction. So this gives n = 2. So take m > 1. Now for each A i , A j , there must be a unique point B ij joined to both A i and A j . B ij cannot be joined to any other A k , for then we would have three points joined to both X and B ij . Finally, A i cannot be joined to any points except X and the B ij , for if it was joined to B, then B is not joined to any other A j (otherwise it would be B ij ). So there is only one point, namely A i joined to both X and B. Contradiction. Now every point is either joined to X or joined to a point which is joined to X (for if X is not joined to Y, then there is a point Z joined to X and Y). So there are no points in the graph except X, the A i and the B ij . So n = 1 + m + m(m-1)/2. Also every A i has degree m (it is joined to X and m-1 points B ij ). X was arbitrary, so we have proved that every two adjacent points have the same degree. Hence all the points have degree m. If m = 2, then n = 4. But we are told n > 4. If m = 3, then n = 7. But B 12 cannot be joined to B 23 or B 13 (or we get a triangle), so it only has degree 2. Contradiction. So there is no graph for n = 7. If m = 4, then n = 11. But B 12 cannot be joined to B 23 or B 24 (or we get a triangle with A 2 ). It cannot be joined to B 14 or B 13 (or we get a triangle with A 1 ). So the only B ij available to it is B 34 and so it has degree < 4. Contradiction. So m ≥ 5. m = 5 gives n = 16. We verify that that works. Join B hi to B jk iff all of h, i, j, k are distinct. Clearly that does not create any triangles. Now consider all possible pairs of unjoined points. Case 1: X, B ij . The only two points joined to both are A i and A j . Case 2: A i , A j . The only two points joined to both are X and B ij . Case 3: A i , B jk (with all i, j, k distinct). Let u, v be the other two suffices. Then B iu , B iv are the only two points joined to A i and B jk . Case 4. B ij and B ik . Again let u, v be the other two suffices (apart from i, j, k). The only two points joined to B ij and B ik are A i and B uv . 11th Balkan 1994 © John Scholes jscholes@kalva.demon.co.uk 11 Apr 2002