Complete graphs
--------------------
In combinatorics, a
graph is a collection of points (the
vertices), some of which are connected by lines (the
edges). The geometric shape of the lines does not matter; all that matters is which vertices they join (see
les Graphes,
Bibliothèque Tangente 54, 2015).
A graph is said to be complete when each of its vertices is connected to every other vertex. The complete graph on n vertices is denoted by Kn.
[/encadre]
First sketches
-------------------
The complete graph on two vertices, denoted by K2, presents no difficulty: simply draw a line segment between two points. K3 is no harder: just draw a triangle—everyone can choose whichever one they find most attractive... With four vertices, the issue of crossings begins to arise. The most common drawing, shown below, contains one crossing.
By arranging the points differently or drawing "less rigid" edges, however, we can avoid crossings. The crossing number of K4 is therefore zero. We write: cr (K4) = 0.
Now consider the complete graph on five vertices. After a few attempts, it seems impossible to avoid at least one crossing between the edges... But can we be certain?
It can be proved that cr (K5) = 1: every drawing of K5 in the plane requires at least one crossing. In fact, by making clever use of a few fundamental results from graph theory, we can go even further. Consider the general case of the complete graph Kn. Each vertex is connected to the other n – 1 vertices, and every edge connects two vertices. The graph therefore has 2n(n−1) edges.
Draw Kn with as few crossings as possible, and treat each crossing as a new vertex. This gives a new graph, denoted by Kn’, with n + cr (Kn) vertices. Since each crossing in the original graph Kn adds exactly two new edges, Kn’ has precisely 2n(n−1)+2cr(Kn) edges.
K5’ has six vertices and twelve edges (and no crossings).
