登机门|登机门CS 2008 |问题85

G是n个顶点和2n–2条边上的图。G的边可以划分为两个边不相交的生成树。以下哪项不适用于G？ （A） 对于k个顶点的每个子集，诱导子图最多有2k-2条边 （B） 最小切入点G至少有两条边 （C） 每对顶点之间有两条边不相交的路径 （D） 每对顶点之间有两条顶点不相交的路径 答复: （D） 说明： 选项D的计数器如下所示。复制两份K4（4个顶点上的完整图形），G1和G2。设V（G1）={1,2,3,4}和V（G2）={5,6,7,8}。利用这两个图G1和G2在一个顶点处合并，即合并（4,5），构造一个新的图G3。结果图是两条边连通的，最小度为2，但存在一个割点，即合并点。

幸亏 伦吉思P 感谢您提供上述解释。 这个问题的小测验