Get every possible (connected) subgraph containing x number of nodes
A standard brute-force method should suffice: enumerate all ${50 \choose 4}$ ways to choose 4 out of the 50 states, and for each such combination, check whether it meets your requirements.  There are only about 230,000 combinations to check, so this should run in a fraction of a second on a computer.

If you wanted to optimize it, there are various methods, such as choosing a state $u$, then choosing another state $v$ that is a neighbor of $u$, then choosing another state $w$ that is a neighbor of $u$ or $v$, then finally one more state $x$ that is a neighbor of one of $u,v,w$, and then checking whether that meets your conditions.  This would be faster.  But why bother?  It's hardly worth spending an extra hour or two programming a complicated algorithm to spend a fraction of a second of CPU time.