1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ $n!*m!$ as a first guess for induced subgraphs? $\endgroup$ – IggyPass Oct 22 '15 at 14:32
  • $\begingroup$ 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. $\endgroup$ – user273952 Oct 23 '15 at 6:09
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ induced subgraph = $2^n$ Spanning subgraph = $2^m$ it is for my question belong to your hint. please explain if i am wrong @martini $\endgroup$ – user273952 Oct 23 '15 at 6:32
  • $\begingroup$ Correct.${}{}{}$ $\endgroup$ – martini Oct 23 '15 at 7:43
  • $\begingroup$ but how to explain the proof ? i am difficult to arrange it $\endgroup$ – user273952 Oct 24 '15 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.