We have a formula to count the number of subgraphs (2 power e-edges) of a simple graph G. Can we count the number of connected subgraph of G? The upper bound is 2 power e. Is it possible to find exact number of connected subgraph of G?
There is no formula that only takes the number of edges and vertices into account. Consider for example the cycle on four vertices, C4, and the paw (a triangle with a degree-one vertex attached to one of the triangle vertices). Both graphs have four vertices and four edges. However, the C4 has four connected subgraphs whereas the paw has only three connected subgraphs.
@Christian Komusiewicz: Please be precise. Your answer is insufficient.
The C4 Graph has 17 connected subgraphs (1 with 4 edges, 4 with 3 edges, 4 with 2 edges, 4 with 1 edge and 4 with 0 edges),whereas the paw has 18 connected subgraphs (1 with 4 edges, 4 with 3 edges, 5 with 2 edges, 4 with 1 edge and 4 with 0 edges) - some of them being isomorphic, some not... (left to you)
@SIMON RAJ F: Not in general-may be for some specific classes of graphs.
Ok, the question was not posed in a completely rigorous manner, so I (unintentionally) made some assumptions (that I should have mentioned). I was assuming spanning connected subgraphs, that is, connected subgraphs that contain all vertices. Furthermore, I counted two subgraphs as different if they are isomorphic but are different when the vertex names are taken into account. Finally, I counted only proper subgraphs.
So for the C4 I can delete any of the four edges but not two or more. For the paw I can delete any of the triangle edges but not two edges and not the edge to the degree-one vertex.
Anyways, the point I was trying to convey still remains correct if the subgraph does not have to be spanning (as you demonstrated).
- Badges
- Science topic