22nd Australian 2001 Problem B4 Find the smallest n such that there is a directed graph on n points such that: (1) there is at most one edge between any pair of points, (2) if there is an edge A to B, then there is a point C such that there are edges A to C and C to B, (3) given any point A, there is a point B such that there is an edge A to B. Solution
: n = 7. There is a solution with n = 7. Label the points 1, 2, 3, 4, 5, 6, 7. Take edges from i to i+1, i+2 and i+4 (subtracting 7 when necessary, so that point 8 means point 1 etc). Obviously (1) and (3) are satisfied. Consider (2). We have to consider three cases. If A is i and B is i+1, then C is i+4, because there is an edge from C to (i+4)+4 = i+1 = B. If A is i and B is i+2, then C is i+1. Finally, if A is i and B is i+4, then C is i+2. So we have to show that any solution has at least 7 points. Take a point 1. By (3), there must be a point 2 with an edge 1 to 2. Now by (2), there must be a point 3 with edges 1 to 3 and 3 to 2. Applying (2) to the edge 1 to 3, there must be a point 4 with edges 1 to 4 and 4 to 3. Note that 4 cannot be 2 because then there would be two edges between 2 and 3 (one each way). Applying (2) to the edge 3 to 2, there must be a point 5 with edges 3 to 5 and 5 to 2. Note that 5 cannot be 1 or 4 because those points already have edges to 3. Applying (2) to the edge 4 to 3, there must be a point 6 with edges 4 to 6 and 6 to 3. Note that point 6 cannot be 2 or 5 because there are already edges 3 to 2 and 5. It cannot be 1 because there is already an edge 1 to 4. Finally, applying (2) to the edge 3 to 5, there must be a point 7 with edges 3 to 7 and 7 to 5. Point 7 cannot be 1, 4 or 6 because there are already edges from those points to 3. It cannot be 2 because there is already an edge from 5 to 2. 22nd Aus 2001 © John Scholes jscholes@kalva.demon.co.uk 25 July 2002