作者nendi (midi)
看板Math
标题[图论] connected 和 paths 两问
时间Sun Mar 18 08:53:27 2012
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
1F：推 XII :1.Menger theorem,2.RHS iff ayclic 03/18 21:31
2F：→ nendi :谢谢楼上 03/18 21:37