I'm trying to understand this following proof:
If $G = <V, E> $ where $\vert V\vert = v$ and $\vert E\vert = e$ and G is simple, prove that $2e \le V^2-V$
In the example I'm following, the author takes the example of this graph:
The author says that, if this was our graph then the number of edges would be equal to $3 \choose 2$. Which is equal to 3, and I don't understand that.
Since our graph is simple, in this example, the max number of edges can only be equal to 1. No?
I need clarification on exactly why the number of edges is equal to $3 \choose 2$ in this example or, in general, $V \choose 2$.
From there, if I have $V \choose 2$ it is easy for me to "convert" it to $\dfrac{V(V-1)}{2}$, so I don't need help on this part.
Thanks.
Let $G$ be a simple graph on $n$ vertices. Notice that each edge is simply a unique pair $(v_i,v_j)$ of vertices. How many distinct pairs of vertices like this are there where we consider $(v_i,v_j) = (v_j,v_i)$? The most basic result in counting is that this is just $\binom{n}{2} = \frac{n^2-n}{2}$. Thus, $e \leq \frac{n^2-n}{2}$ and so $2e \leq n^2 - n$ as desired.