Lower bound of number of independent sets Let $G$ be a connected regular graph with even number of vertices $v$. Also let $i_{v/2}(G)$ be the number of independent sets of $G$ of size $\frac{v}{2}$. Is it possible that $i_{v/2}(G)> 2^{v/2}$?
My hunch is that the answer is no but I cannot prove it.
 A: No, it's not possible. Let's show that $i_{v/2}(G)\le 2$ for all such $G$. 
Let $V$ be the set of vertices of the graph $G$, $U$ be an independent subset of vertices of $G$ of size $v/2$, $W=V\setminus U$, and $d$ be a common degree of a vertex of $G$. Each vertex $u\in U$  is adjacent to $d$ vertices of $V$ and since $U$ is an independent set, all these vertices belong to $W$.  Thus there are $d|U|=dn/2$ edges between $U$ and $W$. Since $|W|=n/2$ and each vertex $w\in W$ is adjacent to $d$ vertices, the number of edges incident to vertices of $W$ is at most $dn/2$ and the equality holds iff each vertex of $W$ is adjacent only to vertices in $U$. Thus the set $W$ is independent too.
So the graph $G$ is bipartite with the partition constituted by $U$ and $W$. We claim that this is a unique partition of vertices of $G$ in two independent subsets $U’$ and $W’$. 
Indeed, without loss of generality we can assume that there exists a vertex $u\in U\cap U’$. Let $v$ be any vertex of $G$. Since the graph $G$ is connected, there exists a path $P$ from $u$ to $v$. Since both $U\cup W$  and $U’\cup W’$ are partitions of $V$ into two independent sets, when we are going along $P$ from $u$ to $v$ at each step we simultaneously switch from $U$ to $W$ and from $U’$ to $W’$ and vice versa. Then we see that $v\in U$ iff $v\in U’$ and $v\in W$ iff $v\in W’$, so $U=U’$ and $W=W’$.
