SKEDSOFT

THE PROBLEM OF RAMSEY :  Prove that at any party with six people, there are three mutual acquaintances or three mutual nonacquaintances.

Solution. This situation may be represented by a graph G with six points standing for people, in which adjacency indicates acquaintance. Then the problem is to demonstrate that G has three mutually adjacent points or three mutually nonadjacent ones.

The complement G of a graph G also has V(G) as its point set, but two points are adjacent in G if and only if they are not adjacent in G. In Figure 28, G has no triangles, while G consists of exactly two triangles.

In figure 29 : A self-complementary graph is isomorphic with its complement. The complete graph Kp has every pair of its P points adjacent. Since V is not empty, P ≥ 1.

Thus KP has lines and is regular of degree P – 1.
As we have seen, K3 is called a triangle. The graphs KP are totally disconnected, and are regular of degree 0.

Theorem 1. The maximum number of lines among all P point graphs with no triangles is
Proof. The statement is obvious for small values of P. An inductive proof may be given separately for odd P and for even P. Suppose the statement is true for all even P ≤ 2n.
We then prove it for P = 2n 2 Thus, let G be a graph with P = 2n 2 points and no triangles. Since G is not totally disconnected, there are adjacent points u and v.
The subgraph G′ = G – {u, v} has 2n points and no triangles, so that by the inductive hypothesis
G′ has at most = n2 lines.
There can be no point W such that u and v are both adjacent to W, for then u, v and w would be points of a triangle in G. Thus if u is adjacent to K points of G′, v can be adjacent to at most 2n – K points. Then G has at most