A graph is called complete if it has no self loops but otherwise has an edge from each vertex to each other vertex. Complete graphs are undirected. The graph I gave earlier as an example of a non-planar graph is complete. The adjacency matrix of a complete graph looks like an identity matrix with the 1’s and 0’s reversed. A complete graph with \({ n }\) vertices, known as a \({ K _ n }\). Our example graph is therefore a \({ K _ 7 }\).
A graph is called bipartite if the set of vertices can be partitioned into two subsets, such that all the edges connect a vertex from one subset to a vertex from the other. An example is the graph above with labelled edges. The two subsets of vertices are \({ \{ a , b , d \} }\) and \({ \{ c , e \} }\), in the labeling from that diagram. This bipartite graph has the property that for every vertex in the first subset and every vertex in the second there is an edge connecting them. That is not a requirement of the definition. A bipartite graph with \({ p }\) vertices in one set and \({ q }\) in the other is called a \({ K _ { p , q } }\). These graphs are often referred to as “complete bipartite” graphs. This terminology is unfortunate, because these graphs are not in fact complete graphs for \({ p > 1 }\) or \({ q > 1 }\), so I won’t use it.
Another example is given in the figure after. In this case it’s easy to see that the graph is bipartite because every edge connects an even numbered vertex to an odd numbered one.
Bipartite graphs arise in a variety of contexts. The one above is related to the finite projective plane of order 2. The even numbered vertices correspond to points and the odd numbered vertices correspond to lines. There is an edge joining two vertices if and only if they correspond to a point and a line through that point.
More generally we can consider graphs whose set of vertices can be partitioned into \({ k }\) disjoint subsets such that no edge connects two vertices in the same subset. Such a partition is called a \({ k }\)-colouring of the graph. A bipartite graph is then one with a \({ 2 }\)-colouring. It’s not terribly difficult to show that every finite planar graph has a \({ 5 }\)-colouring, and indeed to give reasonably efficient algorithms for finding a \({ 5 }\)-colouring for a given graph. It’s considerably more difficult to show that every planar graph has a \({ 4 }\)-colouring. There are planar graphs which can’t be \({ 3 }\)-coloured. Indeed \({ K _ 4 }\) is such a graph. Deciding whether or not a graph has a \({ 3 }\)-colouring is a hard computational problem. Earlier I mentioned that \({ K _ 7 }\) is not planar. In general \({ K _ n }\) can’t be coloured with fewer than \({ n }\) colours so it follows from the Four Colour Theorem that \({ K _ n }\) is not planar for \({ n > 4 }\).