Mathematics Problem Of the Week

Fall 2005

POW #12

Maximal, Planar & Regular

(1) A planar graph is a set of points (vertices) in the plane with lines (edges) drawn between them, such that no two lines cross.

(2) Such a graph is called maximal if no new edge could be added between unconnected vertices without crossing existing edges.

(3) A graph is n-regular if every vertex has exactly n edges from it.

The diagrams below shows maximal 2-regular and 3-regular graphs.

(a) Draw a maximal 4-regular graph with 6 vertices

(b) Draw a maximal 5-regular graph with 12 vertices.

Due Monday, November 28^th at Noon

Solutions should be submitted to Dr. R. Lock's mailbox in the Math office or sent via e-mail to rlock@stlawu.edu.