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!
The proof you have given is much more complicated than need be, and if you are going to go about proving each individual step, you will actually need to display the inductive method that was assumed for the (intuitively obvious) $v=\epsilon +1$ minimization. Furthermore, $\frac{v}{\epsilon}$ is not a particularly rigorous concept, being that it is essentially meaningless beyond potentially human understanding.
What would work much better would be a proof by contradiction:
Assume that there is some $G$ that is both simple and has $\epsilon\gt {v\choose 2}$
If $\epsilon \gt {v \choose 2}=\frac{v!}{(v-2)!2!}=\frac{v(v-1)}{2}=\frac{v^2-v}{2}$
$$2\epsilon \gt v^2-v$$
Each edge requires at least two vertices.
$2\epsilon \gt v^2 - v$
Therfore for $\epsilon \geq 3$ the above isn't true. Therefore we have a contradiction, hence $\epsilon \leq {V \choose 2}$