Question

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

证明：没有3阶子图的完全无向图的子图的n阶简单无向图最多有【n²/4】条边

麻烦各位大大了，谢谢~

Answer 1

解：

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