Problem 1.) What is the crossing number of K5? Prove your claim.

The crossing number of a graph is the least possible number of edge crossings of a plane drawing of the graph. A crossing means a point that is not a vertex where edges meet. The drawing of a graph is made so that no three edges cross at a single point. With this in mind I took a few steps to discovering my answer.

First I started with a shell of the K5 graph with only the points that I would be connecting.

(illustrated below).

Image

To have a complete graph each vertex or point in the graph has to be connected to four other other vertices. This is further broken down by the formula that each vertex should have n-1 edges (5-1=4). After taking this into account I connected all of the points through the outside. (As shown Below)

Image

My next step was to make as many connections as I could without making an edge cross. I tried many different ways to accomplish this and decided to go with the illustration below.

Image

The inside lines are connected without any edge crossings therefor I started to think of other ways to connect the vertices with as little edge crossings as possible. The blue dot represents the vertices that have already completed its n-1 edge connections. The figure below shows the connections after I realized I could not connect anymore on the inside without producing a crossing edge

.Image

There are now only two vertices that have not been completed. There is only one more line that had to be drawn and regardless of if it were on the inside or outside of the pentagon the line would have crossed another making an edge crossing. (Both ways illustrated below) This led me to the answer of 1 crossing for a K5 complete graph.

Image

The red arrows show where the one edge crossing occurs for both cases.

Leave a comment