Question

离散数学无向图转成极大平面图

反自反性，对称性，反传递性
r是自然数集合n上的关系，且xry当且仅当x*2y是奇数
r是实数集合q上的关系，且xry当且仅当y=x/2
如何证明一张无向图为极大平面图
希望能详细解析一下

Answer 1

设G为简单平面图，若在G的任意不相邻的顶点u，v之间加边(u，v)，所得图为非平面图，则称G为极大平面图。

所以可以这样证明：
1，先证明G是平面图
2，证明G的任意不相邻的顶点u，v之间加边(u，v)，所得图H不是平面图

除此之外，还可以用这个充要条件来证明：
设G为n(n≥3)阶简单连通的平面图，G为极大平面图充分必要条件是：
（1） G的每个面的次数均为3.
（2） 设G有m条边r个面，则3r=2m。
（3） 设G有n个顶点，m条边和r个面，则m=3n-6，r=2n-4