极大平面图 定义若G是简单平面图,并且在任意两个不相邻的顶点之 间加一条新边所得图为非平面图,则称G为极大平面图 性质 ●若简单平面图中已无不相邻顶点,则是极大平面图.如 K1,k2K,K都是极大平面图 ●极大平面图必连通 °阶数大于等于3的极大平面图中不可能有割点和桥 设G为m(m≥3)阶极大平面图,则G每个面的次数均为3 任何n(n≥4)阶极大平面图G均有8(O≥3
6 极大平面图 定义 若G是简单平面图,并且在任意两个不相邻的顶点之 间加一条新边所得图为非平面图,则称G为极大平面图. 性质 • 若简单平面图中已无不相邻顶点，则是极大平面图. 如 K1 , K2 , K3 , K4都是极大平面图. • 极大平面图必连通. • 阶数大于等于3的极大平面图中不可能有割点和桥. • 设G为n(n3)阶极大平面图,则G每个面的次数均为3. • 任何n(n4)阶极大平面图G均有δ(G)3
实例 3个图都是平面图,但只有右边的图为极大平面图
7 实例 3个图都是平面图, 但只有右边的图为极大平面图