# Graph theoretical problems

## 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.

## The Attempt at a Solution

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

How to approach this problem if one has no knowledge of complete graphs having $\frac{n(n-1)}{2}$ 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 $\frac{n(n-1)}{2}$ edges and we have to use 7.
It would be 10 choose 7 graphs - but are they all connected?

haruspex