Short note: Planar and regular graphs

Planar graph

A graph that can be drawn in the plane with no edges crossing. For a connected planar graph, Euler's formula holds: v − e + f = 2, and for a simple connected planar graph with v ≥ 3, e ≤ 3v − 6. A graph is planar iff it has no subdivision of K₅ or K₃,₃ (Kuratowski). Examples: trees, cycles and K₄ are planar, while K₅ and K₃,₃ are not.

          a
         / \
        /   \
       /  d  \       d lies inside triangle abc and
      / /   \ \      is joined to a, b and c
     b --------- c

(K₄ drawn with no crossing.)

Regular graph

A graph in which every vertex has the same degree k (a k-regular graph). On n vertices it has nk/2 edges, so nk must be even. Examples: Cₙ is 2-regular, Kₙ is (n − 1)-regular, and the cube Q₃ is 3-regular.

Both: K₄ and the cube Q₃ are regular and planar. K₅ is regular but not planar.