Extremal graphs having no matching cuts
Paul Bonsma, Arthur M. Farley, Andrzej Proskurowski · Journal of Graph Theory · 2011
Abstract A graph G = (V, E) is matching immune if there is no matching cut in G. We show that for any matching immune graph G, |E|≥⌈3(|V|−1)/2⌉. This bound is tight, as we define operations that construct, from a given vertex, exactly the class of matching immune graphs that attain the bound. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:206‐222, 2012 .