Balkan 94/4 solution

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

Answer: n = 16.

Let X be one of the points. Suppose it has degree m, so that it is joined to A₁, A₂, ... , A_m. So no A_i, A_j can be joined (or we would have a triangle XA_iA_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₁₂ cannot be joined to B₂₃ or B₁₃ (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₁₂ cannot be joined to B₂₃ or B₂₄ (or we get a triangle with A₂). It cannot be joined to B₁₄ or B₁₃ (or we get a triangle with A₁). So the only B_ij available to it is B₃₄ 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