※ 引述《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