Question

Proof: Let G be a k-connected k-regular graph. Show that, for any edge e, G has a perfect matching M such that e ε M.

Please show full detailed proof. Thank you in advance!

Answer 1

Solution:

Let G be a K-regular connected bipartite graph with first note that |A| =|B|

since K|A| =    = |E| =  

using Hall's theorem : Hall's theorem tells us there is matching that the matches A if |N(S)| >=|S| ∀ S⊆A . the number of edges from S to N(S) is K(S) and this is the most the number of edges from N(S) to A , which is k[N(S)]. so we have k|S| <= K|N(S)|, which implies |N(S)| >=|S|.

using Konig's  Theorem: We observed that any vertex over c has at least |A| vertices ,since each vertex of C covers exactly K of the K|A| edges then konig's theorem tells that a maximum matching has at least |A| edges, which is only possible if it has exactly |A| =|B| edges,so is perfect. .