[圖論] connected 和 paths 兩問
1.Let G be a 2k-connected graph. Suppose e_1,e_2,...e_k are vertex disjoint
edges of G and v is a vertex of G. Prove that G has k cycles C_1,C_2,..,C_k
such that C_i contains v and e_i, and moreover for i=/=j, C_i and C_j are
vertex disjoint except that they both contain v.
2.Prove that a graph is a forest if and only if every pairwise intersecting
family of paths in G has a common vertex.
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.153.242
推
03/18 21:31, , 1F
03/18 21:31, 1F
→
03/18 21:37, , 2F
03/18 21:37, 2F