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.
Bipartite graphs arise in a variety of contexts. Consider, for example, a graph whose vertices are the possible ways to list the members of a finite set with edges between lists which differ only by swapping the order of a pair of items. This is shown in the diagram. For simplicity I’ve chosen the set of the four letters a, b, c, and d, and have omitted the parentheses and commas from our usual list notation, so \({ ( a , b , c , d ) }\), for example, is represented by \({ a b c d }\).
It’s not obvious staring at this graph that it’s bipartite. One way to show this would be to use different coloured labels for the vertices in the two different sets. Another way to show it is to draw a directed graph which has one edge from each pair in the graph above, chosen consistently to that the set goes from a vertex in one set to a vertex in the other.
In this case, with four members of our set, the graph happens to be a \({ K _ { 6 , 6 } }\), but with more members the graph would not be \({ K _ { p , q } }\) for any choice of \({ p }\) and \({ q }\).