※ 引述《anfranion (安弗尼恩)》之铭言：
: 那个啊，作业二的第八题
: 解答上写 Trivial
: 那如果考试我也可以这样写吗囧
有点冗长 参考看看吧
T = G (V,E) , 对于所有 v 属于 V
deg(v) > 1 < = > v 是 articulation point of T
pf. (=>): 令 T -{v} = G(V',E')
|V'| = |V| - 1
∵ deg(v) > 1
|E'| < |E| - 1 (v的deg.大于一,拿掉v必删掉一个以上的边)
= (|V| - 1 ) - 1 (在T中满足 |E| = |V| - 1 )
= |V'| - 1
= > T -{v} : disconnected (边的个数少于最低需求)
= > v是 articulation point of T
(<=): 首先,对于 V 中任一点 v
deg(v) ≧ 1 since T is connected
再来证明若 v 是 articulation point of T ,则 deg(v) ≠ 1
(证明 ~q -> ~p ) 假设 deg(v) = 1,
= > T - {v} : connected
= > v 不是 articulation point 得证.
since deg(v) ≧ 1 且 若 v 是 T 中的关节点,则 deg(v) ≠ 1
= > deg(v) > 1