In any group of six people, there are three all of whom know each other or three none of whom know each other.

A graph G consists of a set V of vertices (also called points or nodes) and a set E of edges (also called lines or arcs) which are unordered pairs of vertices. We sometimes denote an edge {x, y} as xy. In a drawing of a graph, two vertices x and y are joined by a line if and only if {x, y} ∈ E. If two vertices are joined by a line, they are adjacent ; otherwise, they are nonadjacent . If |V | = p and |E| = q, then we say that G has order p and size q. Some good references on graph theory are [Bol79], [CL96], [CZ05], [Har69], and [Wes95].