定理1：设图G是一个具有n个顶点的连通图，则其边数 e≥n-1 推论1：如果图G是一个具有n个顶点的连通图，并且其边数 e=n1,则图G不含圈，即G是一个树. 证明：（反证法）如果图G含有一个圈，则任意删去圈上的一条边， 图依然连通（为什么？)。但是该图有n个顶点，n-1-1=n-2条边， 与定理1矛盾！ 定理 1：设图 G 是一个具有 n 个顶点的连通图，则其边数 e≥n-1 推论 1：如果图 G 是一个具有 n 个顶点的连通图，并且其边数 e=n-1，则图 G 不含圈，即 G 是一个树. 证明：（反证法）如果图 G 含有一个圈，则任意删去圈上的一条边， 图依然连通（为什么？）。但是该图有 n 个顶点，n-1-1=n-2 条边， 与定理 1 矛盾！