一道离散数学证明题 证明:没有3阶子图的完全无向图的子图的n阶简单无向图最多有【n²⼀4】条边

2024-11-23 09:28:53
推荐回答(1个)
回答1:

解:

因为该完全无向图无3阶子图,所以其子图的n阶简单无向图中n<3,
n-1<=n/2;
n阶简单无向图边数小于或等于n阶完全无向图的边数(【n*(n-1)/2】)
所以没有3阶子图的完全无向图的子图的n阶简单无向图最多有【n²/4】条边