The number of maximal independent sets in connected triangle-free graphs (Q1292823)

The authors show that the maximum number of maximal independent sets possible in a connected triangle-free graph with \(n\geq 22\) nodes is \(5\cdot 2^{(n- 6)/2}\) when \(n\) is even and \(2^{(n- 1)/2}\) when \(n\) is odd. They also characterize the extremal graphs.