Subgraph with same number of edges as original graph

I currently have an efficient algorithm for generating the subgraphs of a graph (using the boost library). My question, the answer to which though seemingly obvious, is more on the theoretical side: can a subgraph S of an undirected, unweighted graph G have the s开发者_运维知识库ame number of edges as G, excluding G itself? There are no constraints on the number of vertices that S can have.

My first guess to the above question would have to be No, but that's based on "common-sense and hand-waving" rather than a rigorous mathematical argument. Does anyone have an alternative answer or know of a mathematical set of criterion that subgraphs must obey?

Thanks, VV

Yes. If G has a isolated vertex (one with no edges in or out) then the subgraph of G obtained by removing that vertex has the same number of edges but strictly fewer vertices.

Suppose G has no isolated vertices. Any (strict i.e. not G) subgraph of G must either contain all the vertices of G or omit some vertex v of G. If the former, it cannot have all the edges of G or it would be G. If the latter, since v has at least one incident edge e (by assumption), the subgraph cannot contain e since it does not contain both of its endpoints; namely, it does not contain v. Hence any subgraph of G has strictly fewer edges than G itself.

Yes - consider a graph G with an isolated vertex. The removal of this vertex gives a proper subgraph of G whose edge set is exactly the same as that of G.

If the graph has no isolated vertices, then the answer is "no": when you remove a vertex, all edges incident to the vertex get removed. Since each vertex has at least one such edge (remember: no isolated vertices), the number of edges is reduced.