Question

一道离散数学图论题，急！！！！！

题目是：
若一无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有几条边?
答案是6.
请问详解是什么？说仔细点，谢谢！

Answer 1

首先知道什么是无向图的补图吧？就是所有节点保留，两点之间有边的，补图里面没边，两点之间没边的，补图里面有边，原图边数＋补图边数等于C(5,2)=10……所以求无向图最多有多少边，就是求补图最少有多少边，既然它说补图是连通的，所以补图最少有4条边（树图），10-4=6，所以原图中最多就有6条边了～

另外这道题是有前提的，就是无向简单图，简单图是指无自环、无平行边。

有问题请补充，满意请采纳～

追问

请问那10是怎么来的？还有另外问一下，已知一个完全图有6个顶点，那它有多少条边呢？谢谢

追答

10就是5点完全无向简单图的边数，就是两两点之间都有边，所以用排列组合得到是10。
6个点的完全图就有15条边。n个点的无向完全简单图有C(n,2)=n(n-1)/2条边。
如果没有学过排列组合，稍微看看书吧。