标签：#图子式

瓦格纳定理

的图子式 (彩色小圆圈和黑色边，删除红色顶点，收缩每个黄色圆圈内的边)。]] 在图论中，瓦格纳理论（）是平面图的禁图表征，以Klaus Wagner的命名。 该定理说：当且仅当有限图的子式不包含完全图K5 或完全二分图K3,3 时候，那么该图就是平面的。 这是图子式论最早的结果之一，也是罗伯逊–西摩定理（Robertson-Seymour theorem）的先驱。 库拉托夫斯基定理的关系 瓦格纳1937年发表了证明。 库拉托夫斯基以前1…