|
|
|
|
|
|
by gjm11
6283 days ago
|
|
|
A graph is nonplanar if and only if it has a subgraph that looks like either (1) five vertices all connected to one another or (2) two sets of three vertices, with every vertex in one set connected to every vertex in the other. "Looks like" means: can be turned into by repeatedly replacing -o- (a vertex with two edges coming out of it) with -- (a single edge between the vertex's two old neighbours). See http://en.wikipedia.org/wiki/Planar_graph for details. |
|
|