※ 引述《chhsiao (bye~)》之銘言：
: ※ 引述《milochen (milochen)》之銘言：
: : 那下面這個圖，有沒有subdivision of K_5 or K_3,3?
: : http://12tv.net/paint_bbs/show.php?index=60
: : 他是不是plannar graph?
: : 我覺得他不是，但又找不到subdivision of K_5 or K_3,3?
: : 謝謝
: 剛要回文 就發現被修文了 :p
: 我找到一個 K_3,3 喔
: 你要不要自己找找 :p
可是這個圖是3-regular
基本上就不用考慮subdivbision 的這一段(如果像你說的那樣disjoint path)
再者來看如果有K_3,3，則必可以找到 u,v兩點
使得他們所有的鄰居都是共有的
也就是說
exist u and v s.t. u的鄰居是 x_1,x_2,x_3且v的鄰居也是x_1,x_2,x_3
But we know that
任取http://12tv.net/paint_bbs/show.php?index=60的其中一點v
此v 必定落在C_4上面
故v的鄰點就已經有兩點落在 包含v的C_4上
故這個問題，我們可以任挑一個C_4,來看，任取一點v in V(C_4)
都找不到u!=v 使得 u與v共同的鄰居相等
故
K_3,3, is not subgraph of http://12tv.net/paint_bbs/show.php?index=60
PS:
小弟覺得不會有subdivision的情形，是因為這graph已經是 3-regular的關係
所以我就是這樣子的關係，又加上真的找不到，所以不知K_3,3在那邊
還請高手多多指教K_3,3 的位置
Thanks