May 7, 2013
Problem of the Week
for Tuesday, May 7, 2013
It is possible to connect every pair of points in a set of four points so that no edge crosses any other edge. The complete graph of order four (K4) is pictured on the left. It is not possible to connect every pair of points in a set of five points without at least one pair of edges crossing each other. The K5 with the one cross-over is pictured on the right. What is the fewest number of edge crossings in a K6 graph? Include a K6 graph with minimum edge crossings in your solution.
