The colorability of a graph depends upon the number (D) of independent
disjoint pairs (D); C = (n - D).
An independent disjoint pair (I) is a special situation. If 1/2 is a
disjoint pair (DP) and 1/3 is also a DP; there is actually only one I,
unless 2/3 is also a DP. Then there are 3 I's Two or more vertices
that are pairwise disjoint are called a set. The number (S)of I's in a
set is calculated by
S = [m^2 - m)/2 where m is the number of vertices
If G is 4-colorable, then D = (n-4)
Suppose that n = 100, then D = 96. There are only 50 ssets with two vertices.
Therefore, larger sets are necessary. There are 33 sets of 3 for a total of
99 I's For n = 100, 6 sets of 4, 28 sets of 3 and 1 set of 2 works perfectly.
If there is a D > 96, then G is 3-colorable and is no D < 97, then G is not
4-colorable!