Assume G is a r-regular bigraph, r 1. Show that a) G admits a 1-factor b) the ed

Question

Assume G is a r-regular bigraph, r 1.

Show that

a) G admits a 1-factor

b) the edge chromatic number of G is r;in other words, G can be decomposed into 1-factor.

Marriage theorem Assume that G is a bigraph and S is a set of its vertexes. We say that a matching M of G covers S if any vertex in S is incident to an edge in M. Given a set of vertexes W in a graph G, the set W" of all vertexes adjacent to at least one of vertexes in W will be called the set of neighbors of W. Note that if G is a bigraph and W lies in the left part then W' lies in the right part. 4.4. Marriage theorem. Let G be a bigraph with the left and right parts L and R. Then G has a matching which covers L if and only if for any subset W C L the set W CR of all neighbors of W contains at least as many vertexes as W; that is,

Explanation / Answer

solution: Both a and b mean the same thing.

as according to question G is a r - regular bigraph,r>=1 So, G has equal size of w and w', so we can produce a matching which covers the left part and the right part thatswhy G admits a 1-factor.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.