满足度数条件的二分图匹配下界证明问询
满足度数条件的二分图匹配下界证明问询
我最近在做图论习题时遇到了一个卡壳的问题,想请教各位大佬:
设$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
相关产品推荐
相关产品推荐

