Let G be a connected bipartite graph (i.e the set of vertices is split as X S Y so that the edges are connecting some pairs xi X with yj Y ).

Let G be a connected bipartite graph (i.e the set of vertices is split as X S Y so that the edges are connecting some pairs xi ∈ X with yj ∈ Y ). Show that if each vertex has multyplicity 3 then there is a complete matching( i.e the number of vertices in X is the same as in Y and there is matching of all vertices in X with vertices in Y )