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?
Best Answer
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$.