$\begingroup$

If I have a graph $\mathbb G$ with $n$ vertices, $m$ edges and $c$ components, how can I count how many spanning subgraphs it has?

Thanks!

$\endgroup$ 2

2 Answers

$\begingroup$

The subgraph has to contain all of the vertices. Then decide for each edge whether it belongs to the subgraph or not, giving $2^m$ possibilities.

$\endgroup$ 3 $\begingroup$

we have m edges. And by definition of Spanning subgraph of a graph G is a subgraph obtained by edge deletion only. If we make subsets of edges by deleting one edge, two edge, three edge and so on. As there are m edges so there are 2^m subsets. Hence G has 2^m spanning subgraphs.

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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