【题目】

由四个不同的点构成的简单无向连通图的个数是（）。

A.32
B.35
C.38
D.41

【解析（1）】

对于三条边用 Cayley 公式：一个无向完全图有 \(n^(n-2)\) 棵生成树；即n个节点的带编号的无根树有 \(n^(n-2)\) 个。

\(n^(n-2)=4^(4-2)=16\)

由于 \(K_3\) 只有3条边，剩下的必然使整张图联通：

\(C_{6}^{4}+C_{6}^{5}+C_{6}^{6}=15+6+1=22\)

\(ans=16+22=38\)

【解析（2）】

4个不同点构成简单无向连通图：
1. 最多可加边的数目（强联通图）：\(\frac{n*(n-1)}{2}=\frac{4*(4-1)}{2}=6\)
2. 最少可加边的数目（树）：\(n-1=4-1=3\)
3. 注意：不是所有的任选3条边都满足条件，在6条边中选3条边会有4种不连通的情况，即3条边连了3个点构成一个环，剩下的一个点被孤立，显然此种情况不能成立。所以需要减去4。

\(ans=C_{6}^{3}-4+C_{6}^{4}+C_{6}^{5}+C_{6}^{6}=38\)