# Thread: Number of subgraphs within a complete graph

1. ## Number of subgraphs within a complete graph

How many subgraphs with at least one vertex does K3 (a complete graph with 3 vertices) have?
I know that K3 is a triangle with vertices a, b, and c. From asking for help elsewhere I was told the formula for the number of subgraphs in a complete graph with n vertices is 2^(n(n-1)/2)

In this problem that would give 2^3 = 8.

However from trying to draw all the subgraphs out by hand using this definition: All the edges and vertices of G might not be present in S; but if a vertex is present in S, it has a corresponding vertex in G and any edge that connects two vertices in S will also connect the corresponding vertices in G. All of these graphs are subgraphs of the first graph.

I was up to 14 subgraphs. From what I understand, the graph itself is a subgraph of K3 (1), the graph with 3 vertices and no edges is a subgraph of K3 (2), a by itself is a subgraph of K3 (3), b by itself is a subgraph of K3 (4), c itself is a subgraph of K3 (5), a and b connected is a subgraph of K3(6), a and c connected is a subgraph of K3(7), a and b by themselves are a subgraph of K3 (8), a and c by themselves are subgraph of K3 (9), etc. I'm failing to understand why some of the graphs I listed are not subgraphs of K3, since they either preserve some of the vertices in S, and any edges in the subgraphs listed are also preserved in K3.

Any help is greatly appreciated.

2. ## Re: Number of subgraphs within a complete graph

Originally Posted by JK94
How many subgraphs with at least one vertex does K3 (a complete graph with 3 vertices) have?
I know that K3 is a triangle with vertices a, b, and c. From asking for help elsewhere I was told the formula for the number of subgraphs in a complete graph with n vertices is 2^(n(n-1)/2)
In this problem that would give 2^3 = 8.

Do you understand the logic behind the formula $\displaystyle 2^{\frac{n(n-1)}{2}}~?$

That is the number of subsets of a set of $\displaystyle \binom{n}{2}$ which is the number if edges in $\displaystyle \mathcal{K}_n$.

This $\displaystyle 2^3$ is correct.

3. ## Re: Number of subgraphs within a complete graph

Originally Posted by Plato
Do you understand the logic behind the formula $\displaystyle 2^{\frac{n(n-1)}{2}}~?$

That is the number of subsets of a set of $\displaystyle \binom{n}{2}$ which is the number if edges in $\displaystyle \mathcal{K}_n$.

This $\displaystyle 2^3$ is correct.
I understand that formula and I understand that it applies here as well. However I am simply trying to figure out why some of those relationships I listed are NOT sub-graphs. It seems to me they satisfy the conditions needed for a sub-graph-- namely that "All the edges and vertices of G might not be present in K; but if a vertex is present in K, it has a corresponding vertex in G and any edge that connects two vertices in S will also connect the corresponding vertices in G."

,
,

,

,

,

,

,

,

,

,

,

,

,

,

# Formulas of finding subgraphs

Click on a term to search for related topics.