You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

满足度数条件的二分图匹配下界证明问询

满足度数条件的二分图匹配下界证明问询

我最近在做图论习题时遇到了一个卡壳的问题,想请教各位大佬:

设$G$是一个有$n$个顶点的二分图,每个顶点的度数为3或4。证明$G$存在一个大小至少为$\frac{3n}{7}$的匹配。

我自己尝试从之前学过且已经证明过的二分图结论入手:对于任意二分图$G$,都存在一个匹配$M$满足:
$$|M| \geq \frac{E(G)}{\Delta(G)}$$
这里$\Delta(G)$表示图$G$的最大度。

目前我想着分情况讨论,比如先考虑$G$是3-正则图的情况,但后续推导就断了。想问问大家这个思路是否可行?或者有没有其他更顺畅的方法来完成整个证明?

备注:内容来源于stack exchange,提问作者JLGL

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.16 02:44:52