Can a Graph Have m Times More Edges Than Vertices?

[nuuskur]

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 \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]

How to approach this problem if one has no knowledge of complete graphs having n(n−1)/2 edges?

It's not something you need prior knowledge of. You only need to find one example. If you start in the obvious way, looking for an example in which every vertex has r edges, it is easy to see that r =2m and should be apparent that a graph of r+1 vertices all interconnected is an example.

How to calculate the number of possible graphs given the number of vertices and edges?

That's a very hard problem, unless you are supposed to regard the vertices as distinct. In which case, the question would have been better worded as the number of graphs with m edges that can be formed on n labelled vertices.

Connected graphs, disconnected graphs.

Not sure what this clause means. Does it mean counting those cases separately or counting them all together? You have interpreted it as separately, so I'll assume that's right.
Clearly they aren't necessarily all connected in general. For 5 vertices and 7 edges, they will all be connected. (Suppose such a graph is not connected, falling into k and n-k vertex sets. What's the maximum number of edges?) But for 4 to 6 edges on 5 vertices there can be both connected and disconnected graphs.
Sounds like an application of inclusion-exclusion.