看到 P443P_{443}P443,例题Knights of the Round Table引理1:若两个骑士属于两个不同的“点双连通分量”,则他们不可能一起出席会议。
Knights of the Round Table
这是错误的!反例:
考虑有9个点,11条边如下:
1 2 2 3 3 1 3 4 4 5 5 6 6 7 7 3 5 8 8 9 9 5
此时共有3个点双连通分量:
1.1 2 3 2.3 4 5 6 7 3.5 8 9
而1号点双的3号点与3号点双的5号点可以一起参加会议,即3 4 5 6 7这5人参加。