On the Number of Dependent Sets in a Connected Graph

A set \(X\) of vertices of a graph is said to be dependent if \(X\) is not an independent set. For the graph \(G\), let \(P_k(G)\) denote the set of dependent sets of cardinality \(k\).

In this paper, we show that if \(G\) is a connected graph on \(2n\) vertices where \(n \geq 3\), then \(|P_n(G)| \geq |P_{n+1}(G)|\). This study is motivated by a conjecture of Lih.