Tutte sets in graphs I: Maximal tutte sets and D‐graphs

A well‐known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency of G . A subset X of V ( G ) for which this deficiency is attained is called a Tutte set of G . While much is known about maximum matchings, less is known about the structure of Tutte sets. In this article, we study the structural aspects of maximal Tutte sets in a graph G . Towards this end, we introduce a related graph D ( G ). We first show that the maximal Tutte sets in G are precisely the maximal independent sets in its D ‐graph D ( G ), and then continue with the study of D ‐graphs in their own right, and of iterated D ‐graphs. We show that G is isomorphic to a spanning subgraph of D ( G ), and characterize the graphs for which G ≅ D ( G ) and for which D ( G )≅ D 2 ( G ). Surprisingly, it turns out that for every graph G with a perfect matching, D 3 ( G )≅ D 2 ( G ). Finally, we characterize bipartite D ‐graphs and comment on the problem of characterizing D ‐graphs in general. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 343–358, 2007