《集合论与图论》课堂练习3参考模板范本.doc

集合论与图论课堂练习3集合论与图论课堂练习3学号 姓名 一、判断下列命题是否正确，并说明理由。（括号内写“是”或“否” ）（40分，每题8分，是非判断4分，证明或反例4分）1 存在7个结点的自补图。（ 否 ）/*西安交通大学1999*/自补图对应的完全图的边数必须是偶数，而7个结点的完全图的边数为21。2 设G是顶点数的连通图。则G没有割点当且仅当G的剖分也没有割点。（真）如果G的剖分有割点，则G有割点，矛盾；所以G没有割点，则G的剖分也没有割点。如果G有割点，则该割点为G的剖分的割点，所以G的剖分有割点，矛盾；所以G的剖分也没有割点则G没有割点。3 若G是简单连通图，边数为e，结点数为n。若en，则G至少有3棵生成树。（ 是 ）/*复旦大学1998*/*只需证明e=n时，命题成立*/若e=n-1，因为G是连通的，所以为一棵树；再添加一边时，因为G是简单图，所以图中必存在一个长度大于等于3的回路，则