On the Number of Dependent Sets in a Connected Graph

Abstract

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\ge 3$, then $|P_n(G)|\ge |P_{n+1}(G)|$. This study is motivated by a conjecture of Lih.