2008/08/11
planarity
今日507であったネタ
以下のグラフは平面的グラフ?
V={0,1,2,3,4,5,6,7}
E={(0-1),(0-3),(0-4),(1-2),(1-5),(2-6),(2-3),(3-7),(4-5),(4-6),(5-7),(6-7)}
つまりはこのようなグラフ
少し考えて, 平面的ではないという結論に至ったが, このグラフはサブグラフにK5やK3,3を持ってないのも明らか
さて, どこが間違ってるんでしょうかねぇ
参考リンク: Wikipedia:平面グラフ