-2
$\begingroup$

I was just going through a past exam paper for my intro graphs module and the following question came up, and I can't find any notes on it:

Let G = (V,E) be a simple graph. Show that:

$2|E| \leq |V|^2 - |V|$

any ideas?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
1
$\begingroup$

Equality holds for complete graphs. Since $G$ is simple, it's the subgraph of some complete graph $K_n$. So $|E(G)| \leq |E(K_n)|$ and the inequality follows.

Improve this answer
$\endgroup$
0
$\begingroup$

Cp. Bondy/Murty "Graph Theory with Applications", Ex. 1.1.3 (so it must be easy), available online ... but you do know what a simple graph is ? (Probably the question does not really belong here, being of such a trivial nature ?) Kind regards, Stephan.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .