What can we determine if we are given only the number of edges and vertices of a graph?

Question

Given that the number of edges in a simple graph G having 10 vertices is 37, what can we infer from this piece of information?

I could guess that since the number of vertices is 10, the number of permissible edges have to be from zero to $10\choose{2}$.

So we know that G isn't a complete graph. How can we find out more details like if it is connected or disconnected? or is it a closed graph?

Thanks.

Answer 1

Well, I'm sure there is plenty of information you can obtain, depending on other assumptions and what you'd like to prove.

Assuming $G$ is a simple graph on $10$ vertices with $37$ edges:

1. From almagest's comment: A component of size $9$ can have at most $\binom{9}{2} = \frac{9\cdot 8}{2} = 36$ edges (this is sort of a "maximum" case if we were attempting to add edges in a way to get a $G$ that is disconnected). But we have $37$ edges, so we are forced to connect the isolated vertex. This is the same line of thinking in one can use to prove $\delta (G) \ge (n-1)/2 \implies G$ connected.
2. $G$ has too many edges to be planar, since $|E(G)| = 37 \not \le 3|V(G)|-6 = 24$. This is derived from Euler's formula (same link, different section). Because $G$ is non-planar, it contains a sub-division of $K_5$ or $K_{3,3}$. Be careful, using this inequality one can only prove that a graph is non-planar if it has too many edges, you cannot say that $G$ is planar if it satisfies the inequality. However, the inequality can be strengthened under other assumptions, for example if $G$ is triangle-free and planar, $|E(G)| \le 2|V(G)|-4$.
3. Turan's Theorem. Too many edges implies existence of a particular clique.

Using 1., we can see that $G$ is not a tree or forest (more than $|V(G)|-1$ edges and connected), and therefore contains a cycle. You can also compute quantities like the average degree, $2|E(G)|/|V(G)|$, which may be useful. At this point, we can just list random things.

You can find more information, but these three are the main things that come to my mind when thinking about the number of edges in a graph.

Answer 2

The graph must be connected.
A graph may be decomposed into several islands(which are connected ie there exists a path from a to b on the island for all vertices a&b on the island). For example a graph of 4 vertices , with edges 1-2 , and 3-4 , may be thought to be the 'sum' of a two subgraphs 1-2(two vertices and one edge) and 3-4(similar explanation)

lets say that your graph of 10 vertices is decomposed in a similar manner. Now, the largest of the sub-graphs may have 9 vertices. Which means, it may have at most $\binom{9}{2}$ = 36 edges. This is true, regardless of my choice of the 9 vertices, meaning it is valid for all combinations chosen. This means, it is impossible to construct a 10 vertex graph , and choose a group of 9 and 1 vertices to create two disconnected subgraphs. They have to be connected by one edge.

A similar explanation may be given if we were to divide the graph into smaller components of all other sizes, 8&2, 7&3 , etc. since it is always true that

$$\binom{n}{2}+ \binom{10-n}{2} \le \binom{9}{2} + 1 $$ with bound for n being n $\le$ 9 and $\ge$ 1

this may be proven mathematically, as the equation simplifies to :

$$ n^2 - 10n + 8 \le 0 $$

which if we find zeroes , is about 0.87 and 9.12 , which are outside our bounds for n. Hence we may conclude, there is no configuration of two disconnected islands that may be formed, in a graph that has 37 edges and 10 vertices.