离散数学 匹配
(1)设G是以(X,Y)为二部划分的二部图，对X的 每个非空子真子集S都有 |N（S）|?|S | 。证明，对G的任意一条边e，都有一个饱和X的匹配M，使得e∈M (2)二部图G有m条边，最大度为 Δ，则G有 一个不少于m/Δ 条边的匹配。 (3)G是完全二部图Kn ,n 的子图，G的边数 m?(k−1)n。证明G有一个至少k条边的匹 配。
(1)直接用Hall's theorem （3）可以直接用(2)推出：注意到Δ=m/Δ>=m/n>(k-1)，所以至少有个大小为k的匹配。 (2)可以用Konig's theorem推出：Konig's theorem说最大匹配的边的个数等于size of minimum vertex cover（实在不会翻译了。
。。） 对于一个vertex cover, 每个边都至少有一个端点在这个cover里，而每个点的度数至多是Δ，所以这样的cover至少要m/Δ个。Konig's theorem指出最大匹配的大小和这个最小的cover一样大，所以最大匹配大小至少是m/Δ。
PS: For 1。 Soconsidere=uv,uisinX,considerthegraphG'withu,vremovedfromG。ConsiderX\u,foreverysubsetSofX\u,|N'(S)|( e#ofneighborsofSinG')isatleast|N(S)|-1(sinceonlyvisremovedfromY)。
By |N(S)|>|S|, |N'(S)|>=|N(S)|-1>=|S|, this invokes the Hall's theorem and we get a perfect matching in G'。 edge uv is not in G', add it back we get a perfect matching for G。
Sorry I don't have Chinese input here。。。 Please let me know if this clarifies your question。
答：不可能。 如果这样一个序列d1,d2,...,d(n)可以构成无向简单图，那么对每个顶点，因为没有重边和到自身的环，所以其度数最多是n-1. 现在有n个不等的正...详情>>
答：详情>>
