正则图G的边数m的最小值是多少?

发布网友发布时间：2024-04-11 13:27

共1个回答

热心网友时间：2024-05-14 00:22

n阶k-正则图G的边数m＝n(n－1)/2
证明:一共有n个点，第一个点与其他点有n－1条连线，第二点与其他点有n－2条连线(是因为除去了与第一个点相连的那条线，否则会边会计算重复)……第n－1个点只能与最后一个点相连接也就是1条线，第n个点就不连接了，所以所有边m＝(n－1)＋……＋2＋1(等差数列求和)
要不你理解为假设有n个人参加会议，每两个人之间都握手一次，不重复握手，求会议上握手的总次数。可以想象为n个人站在一排，第1个人去和其他人依次握手(共n－1次)，握完之后就可以离开了，第2个人在依次去握手时明显少了一个，因为第1个人已经和所有的人都握过了，不需要再和第2个人握手，所以就是(n－1)＋(n－2)＋……＋2＋1