上次写离散已经是4周之前了…
1.
n个点的图最多有n-2个割点。
构造方法：将n个点连成链，除2个端点外，都是割点。
上界证明
首先删去图中的所有重边和自环，这对割点个数无影响。
引理
对于一个连通图，生成树的叶节点都不是割点。
证明：删去生成树的某一个叶节点，其他点对仍然可以通过树边相连通，因此叶节点不是割点。
主要证明
若G没有边，则每个点都不是割点。
否则，考虑G的某个点数大于1的连通块，任取它的某个生成树，由于点数大于1的树至少有两个度数为1的点，因此G至少有两个点不是割点，因此n-2是割点个数上界。
n个点的图最多有n-1条割边。
构造方法：将n个点连成链，有n-1条边，每条边都是割边。
上界证明：若有条割边，则割边会形成环，这与割边的定义矛盾。
4.
G是2-连通图当且仅当G的任意两节点之间至少有两条不相交的道路。
充分性
因为任意两节点之间至少有2条不相交的道路，所以删去任意一点后，任意两节点之间至少有1条道路，因此即.
必要性
假设u,v之间不存在2条不相交的道路，则删去u,v之间道路的某个公共点，u,v不连通。因此，矛盾。因此原命题成立。