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\cong D(G)$ and for which $D(G)\cong D^2(G)$. Surprisingly, it turns out that for every graph $G$ with a perfect matching, $D^3(G)\cong D^2(G)$. Finally, we characterize bipartite $D$-graphs and comment on the problem of characterizing $D$-graphs in general.