In class we noted that every nonplanar graph contains an edg

In class we noted that every non-planar graph contains an edge so that if we erase this edge then the crossing number of the new graph is smaller.

• Is there a graph such that no matter which edge is deleted the crossing number of the new graph is smaller?

• Is there a graph such that no matter which edge is deleted the crossing number of the new graph reduces by two or more?

Solution

Draw a triangle, draw a vertex in the middle of the triangle. Include the remaining edges. Draw a triangle, draw a vertex in the middle of the triangle. Include the remaining edges.