How many subgraphs does a $4$-cycle have? Question: How many subgraphs does a $4$-cycle have? 
I am trying to discover how many subgraphs a $4$-cycle has. I know that there will be $2^4=16$ subgraphs with no edges, but I am not sure how to determine how many subgraphs there will be with $1$, $2$, $3$, or $4$, edges.
Originally I thought that there would be $4$ subgraphs with $1$ edge ($3$ that are essentially the same), $4$ subgraphs with $2$ edges, $44$ subgraphs with $3$, and $1$ subgraph with $4$ edges. Giving me a total of $29$ subgraphs (only $20$ distinct). However, this is not he correct answer. What are your thoughts? 
 A: I assume you asked about labeled subgraphs, otherwise your expression about subgraphs without edges won't make sense.
Subgraphs without edges. You're right, their number is $2^4 = 16$.
Subgraphs with one edge. You choose an edge by 4 ways, and for each such subgraph you can include or exclude remaining two vertices. The total number of subgraphs for this case will be $4 \cdot 2^2 = 16$.
Subgraphs with two edges. There are two cases - the two edges are adjacent or not. If the two edges are adjacent, then you can choose them by 4 ways, and for each such subgraph you can include or exclude the single remaining vertex. The number of such subgraphs will be $4 \cdot 2 = 8$. If edges aren't adjacent, then you have two ways to choose them. The total number of subgraphs for this case will be $8 + 2 = 10$.
Subgraphs with three edges. You just choose an edge, which is not included in the subgraph. The total number of subgraphs for this case will be $4$.
Subgraphs with four edges. The original cycle only.
Total number of subgraphs of all types will be $16 + 16 + 10 + 4 + 1 = 47$.  
A: The question already has an excellent answer, but I want to show another route that gives the same number. (The point is that in combinatorics there is often not just "the" solution, but many correct solutions, and if they are correct they must lead to the same number. Counting in two or more different ways is often a good error check.)
You can choose 0, 1, 2, 3 or 4 vertices.
0 vertices. No edges can be chosen, so 1 way to choose.
1 vertex. 4 such vertex sets. No edges. So 4 ways.
2 vertices. They can be adjacent in the original graph (4 ways) or diagonally opposite (2 ways). In the former case the edge can be taken or not (2 ways). In the latter case they don't have an edge (1 way). In total $4 \times 2 + 2 \times 1=10$ ways.
3 vertices. Four ways to choose them. In each case they have two edges in the original graph, so $2^2=4$ ways for which edges are taken. In total $4 \times 4 = 16$ ways.
4 vertices. One such vertex set, but $2^4=16$ ways in which of the four edges are taken.
Adding up: $1+4+10+16+16 = 47$.
