Question: Does this proof hold? Is this a bad proof? Any nicer proofs that don't rely on other theorems?
Notation:
- $\epsilon$ – Number of edges
- $v$ – Number of vertices
- G – Here, any Graph
If $G$ is simple, then $\epsilon \leq {v \choose 2}$
Proof: For each simple graph we have no loops, and only one edge connecting each pair of vertices. A graph with no isolated vertices and all vertices connected to a single vertex will minimise $\frac{v}{\epsilon}$ in this case we can see:
- $\epsilon = 1 \implies v=2$
- $\epsilon = 2 \implies v=3$
- $\cdot$
- $\cdot$
- $\epsilon = n \implies v= n+1$
So $v = \epsilon +1$ in the minimal $\frac{v}{\epsilon}$ case, and hence:
$\epsilon \leq {{\epsilon + 1} \choose 2} =\frac{(\epsilon + 1)!}{(\epsilon -1)! 2!}=\frac{(\epsilon + 1)\epsilon}{2}=\frac{\epsilon^2 + \epsilon}{2}$
$$\epsilon \leq \frac{\epsilon^2 + \epsilon}{2} $$
$$2\epsilon \leq \epsilon^2 + \epsilon$$
$$\epsilon \leq \epsilon^2$$
$$1 \leq \epsilon$$
Which is true.
Therefore, $G$ being simple implies $\epsilon \leq {v \choose 2}$
Thank you!
Best Answer
I don't really follow your argument, but it seems like you're making this much more complicated than it is. If a graph is simple, then an edge is determined by a pair of vertices. Since there are only $\binom{v}{2}$ pairs of vertices, there can be no more than $\binom{v}{2}$ edges.