How many subgraphs with exactly 6 edges can I make from a complete graph with 7 vertices?

65 Views Asked by At

Let the complete graph be unweighted and undirected. The subgraphs can be unconnected.

Edit (More detail): I'm trying to go about this by splitting it up into spanning trees and non-spanning trees because spanning trees also have 6 edges. Therefore...

# of subgraphs with 6 edges = # of Spanning Trees + # of Non-Spanning Tree with 6 edges

The number of spanning trees is equal to $V^{V-2} = 7^5=16807$ where V is the number of vertices. So, I need to find the number of non-spanning trees, but I don't know where to go from there.

1

There are 1 best solutions below

2
On BEST ANSWER

I think you are overthinking this. It's just the number of ways to choose $6$ edges from the $(7 \times 6 )/ 2$ edges in the complete graph.