The typical structure of maximal triangle-free graphs

Recently, settling a question of Erdos, Balogh, and Petřríčková showed that there are at most 2 ^n2/8+o(n2) n-vertex maximal triangle-free graphs, matching the previously known lower bound. Here, we characterize the typical structure of maximal triangle-free graphs. We show that almost every maximal triangle-free graph G admits a vertex partition X ∪ Y such that GTXU is a perfect matching and Y is an independent set. Our proof uses the Ruzsa-Szemerédi removal lemma, the Erdos-Simonovits stability theorem, and recent results of Balogh, Morris, and Samotij and Saxton and Thomason on characterization of the structure of independent sets in hypergraphs. The proof also relies on a new bound on the number of maximal independent sets in triangle-free graphs with many vertex-disjoint P ₃s, which is of independent interest.