# Finding the subgraphs of a simple graph.

• December 3rd 2012, 07:17 PM
Kevmck
Finding the subgraphs of a simple graph.
I've been stumped trying to figure out how to solve this question and I've received conflicting advice. I'm wondering which is correct, and how do actually go about solving this question.

"Let G be a simple graph with m edges and n vertices. How many different subgraphs with n vertices does G have?"

I'm given the following equation for assistance:

If $G = (V, E)$ is a graph (directed or undirected), then $G_1 = (V_1, E_1)$ is called a subgraph of G if $0 \neq V_1 \subseteq V$ and $E_1 \subseteq E$, where each edge in $E_1$ is incident with vertices in $V_1$
• December 4th 2012, 05:15 PM
coolge
Re: Finding the subgraphs of a simple graph.
This is a simple combinatorial problem. Each of the $m$ edges may or may not be included in a subgraph. That gives you $2^m$ possibilities. (The assumption is that isomorphism is not taken into consideration.)