CSP-S 2020 第一轮 第8题：二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简

题目

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，$24$ 个顶点的二分图至多有（ ）条边。

选项

• A. 144
• B. 100
• C. 48
• D. 122

答案

A

题解

选 A. 144。

设二分图两部分分别有 \(x\) 和 \(24-x\) 个顶点。因为边只能连接不同部分的顶点，所以最多有 \[ x(24-x)=144-(x-12)^2\le 144 \] 条边。

当两部分各有 \(12\) 个顶点，且两部分之间所有可能的边都连上时，恰好有 \(12\times12=144\) 条边。