[圖論]一個和cubic bipartite 有關的問題

[nendi (midi)]

想請教  a cubic (3-regular) bipartite graph G, V(G) = (X,Y)

其中 X和Y的個數皆為3k, k屬於正整數

是否一定會存在一組  x_1,x_2 .... x_k \in X

                  k
使得  Y 被包含在  U  N(x_i)
                 i=1

並且  N(x_1),N(x_2),...,N(x_k) 為一 disjoint set 呢？







感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.175.228.16
→ arthurduh1  :|X| = |Y| = 3k 不太對唷
→ nendi       :那個3k 是給定假設的條件 @@
→ nendi       :假設 X 和 Y 皆為3倍的個數
推 Scape       :k=1時就不會了不是嗎？K_3,3 是complete bipartite
推 Scape       :而在同一個independent set裡的點(就是你說的X或Y)
→ Scape       :他們的neighbor都是一樣的，交集非空
推 Scape       :甚至用3regular的條件可以簡單推出點跟邊個數之間的
→ Scape       :關係，也可以知道這樣的disjoint set根本不存在
→ nendi       :給樓上，k3,3 的任意一個點都會把對面的三個點包含在
→ nendi       :那個點的neighborhood 裡面
推 Scape       :sorry  我看錯了。以為你的x_i是指X裡的全部元素
→ sneak       : 假設 X 和 Y 皆為 https://daxiv.com
→ sneak       : k=1時就不會了不是嗎 https://noxiv.com
→ muxiv       : //daxiv.com https://moxox.com