A graph with n points satisfies the following conditions: (1) no point has edges to all the other points, (2) there are no triangles, (3) given any two points A, B such that there is no edge AB, there is exactly one point C such that there are edges AC and BC. Prove that each point has the same number of edges. Find the smallest possible n.
Solution
Answer: 5.
We say A and B are joined if there is an edge AB. For any point X we write deg X for the number of points joined to X. Take any point A. Suppose deg A = m. So there are m points B1, B2, ... , Bm joined to A. No Bi, Bj can be joined for i ≠ j, by (2), and a point C ≠ A cannot be joined to Bi and Bj for i ≠ j, by (3). Hence there are deg Bi - 1 points Cij joined to Bi and all the Cij are distinct.
Now the only points that can be joined to Cij, apart from Bi, are other Chk, for by (3) any point of the graph is connected to A by a path of length 1 or 2. But Cij cannot be joined to Cik, by (2), and it cannot be joined to two distinct points Ckh and Ckh' by (3), so it is joined to at most one point Ckh for each k ≠ i. But by (3) there must be a point X joined to both Bk and Cij (for k ≠ i), and the only points joined to Bk are A and Ckh. Hence Cij must be joined to at least one point Ckh for each k ≠ i. Hence deg Cij = m.
But now if we started with Bi instead of A and repeated the whole argument we would establish that deg Bi is the same as the deg Chk, where Chk is one of the points joined to Ci1. Thus all the points have the same degree.
Suppose the degree of each point is m. Then with the notation above there is 1 point A, m points Bi and m(m-1) points Cjk or m2 + 1 in all. So n = m2 + 1. The smallest possible m is 1, but that does not yield a valid graph because if does not satisfy (1). The next smallest possibility is m = 2, giving 5 points. It is easy to check that the pentagon satisfies all the conditions.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002