Matching transformation graphs of cubic bipartite plane graphs

AbstractIn this paper, we explore some properties of the matching transformation graph of a connected cubic bipartite plane graph G. We prove that if M is any perfect matching of G, then G has at least two disjoint M-alternating faces. This result is sharp in the sense that there are connected cubic bipartite plane graphs which do not have three disjoint M-alternating faces for some perfect matching M. We also show that the matching transformation graph of G is 2-connected