NOIP 提高 2010 第一轮 第 22 题：无向图G有7个顶点，若不存在由奇数条边构成的简单回路，则它至多有

题目

无向图 $G$ 有 $7$ 个顶点，若不存在由奇数条边构成的简单回路，则它至多有条边。

答案

12

题解

考点定位

本题考「二分图最大边数」,对应大纲 3.3.1 图的概念（难度【3】）。

解题过程

无奇回路 ⟺ 二分图。7 点二分图边数 ≤ x(7−x)，x=3/4 时最大 3×4=12（K₃,₄）。

答案：12。

易错提醒

① 奇圈 ⟺ 非二分图；② 两部分均分时乘积最大（这里 7/2=3.5，取 3 和 4）。