- #1

- 854

- 901

## Homework Statement

#1 Does there exist a graph that has m times more edges than vertices?

#2 How to calculate the number of possible graphs given the number of vertices and edges? Connected graphs, disconnected graphs.

## Homework Equations

## The Attempt at a Solution

#1We know that a complete graph has [itex]\frac{n(n-1)}{2}[/itex] number of edges, n being the number of vertices in the complete graph. Hence [itex] m = \frac{n-1}{2} \Leftrightarrow n = 2m + 1[/itex].

How to approach this problem if one has no knowledge of complete graphs having [itex]\frac{n(n-1)}{2}[/itex] edges?

-------

#2 A connected graph is such a graph whose every 2 vertices can be connected via a path.

If we have, say, 5 vertices and 7 edges.

Well, from the complete graph we know there are total of [itex]\frac{n(n-1)}{2}[/itex] edges and we have to use 7.

It would be 10 choose 7 graphs - but are they all connected?