The Number of Maximal Independent Sets in Triangle-Free Graphs

Abstract

In this paper, it is proved that every triangle-free graph on $n \geq 4$ vertices has at most $2^{n /2} $ or $5 \cdot 2^{( n - 5 )/2} $ independent sets maximal under inclusion, whether n is even or odd. In each case, the extremal graph is unique. If the graph is a forest of odd order, then the upper bound can be improved to $2^{( n - 1 )/2} $.