同态
如果两个图G1和G2是同构的,则可以通过将G的某些边除以更多的顶点而从同一图'G'中获得每个图。看下面的例子-
通过添加一个顶点将边缘“rs”划分为两个边缘。
下面显示的图形与第一个图形同构。
如果G1与G2同构,则G与G2同胚,但是反之则不必成立。
具有4个以下顶点的任何图形都是平面的。
任何具有8个以下边缘的图形是平面的。
当且仅当n≤4时,完整图Kn是平面的。
当且仅当m≤2或n≤2时,完整的二部图Km,n是平面的。
具有最小顶点数的简单非平面图是完整图K5。
边数最少的简单非平面图是K3,3。
多面图
如果每个顶点的度数≥3,即deg(V)≥3∀V∊G,则简单的连接平面图称为多面体图。
3|V|≤2|E|
3|R|≤2|E|