# How many induced subgraph dan spanning subgraphs does G have

Let $G = (V,E)$ and $H = (U,F)$ be two graphs. if $U \subseteq V$ and $F \subseteq E$, than we say that $H$ will be subgraph of $G$.

1. $H$ is an induced subgraph if for any $u,v \in U$, $\{u,v\} \in F$ if and only if $\{u,v\} \in E$.

2. $H$ is a spanning subgraph if $U = V$.

Suppose that a graph $G$ has $n$ vertices and $m$ edges. How many induced subgraphs does $G$ have? How many spanning subgraphs does $G$ have?

• $n!*m!$ as a first guess for induced subgraphs? – IggyPass Oct 22 '15 at 14:32
• is it correct if $2^m$ can use to know the number of spanning subgraphs does $G$ have. it's because the subgraphs have contain all of the vertices. – user273952 Oct 23 '15 at 6:09

Hint. An induced subgraph is uniquely determined by its vertices, that is $G$ has as many induced subgraphs as $V$ has subsets. Likewise the spanning subgraphs correspond to subsets of $E$.
• induced subgraph = $2^n$ Spanning subgraph = $2^m$ it is for my question belong to your hint. please explain if i am wrong @martini – user273952 Oct 23 '15 at 6:32
• Correct.${}{}{}$ – martini Oct 23 '15 at 7:43