Edit made on August 18, 2011 by ColinWright at 21:01:23
Deleted text in red
/
Inserted text in green
WW WM
HEADERS_END
In graph theory, a planar graph is a graph which can be embedded in the plane i.e. plane.
That is, it can be drawn on the plane so that its edges intersect only at its
nodes. (see embedding).
Kuratowski's theorem states that a graph is planar if and only if it does not
contain a topological EQN:K_5 or EQN:K_{3,3}. Showing that EQN:K_5 and EQN:K_{3,3}
are non-planar is fairly easy using the Euler characteristic of the plane
/(V+R=E+2)/ but proving the other direction is decidedly awkward.