you can prove it by taking some set of vertices say four (v1,v2,v3,v4).
Now you are asking of Big Oh(greatest upper bound ...tightest most precisely )
note:this prove is for simple graph(see wiki)
now place the vertices like:
v1 v2
v4 v3
{in shape like rectangle}
just think what will be maximum number of edges possible? hmmm answer is :
if we draw an edge between every pair of vertices.
for v1 : edges can be v(1->2) ,v(1->3),v(1->4)
for v2: edges can be v(2->1){already included therefore don't write
it} ,v(2->3),v(2->4)
for v3:edges can be v(3->4)
for v4: all are already included
what u see?
total no of edges are coming in form:3+2+1=6
for n vertices(v1,v2......,vn) same could be done:
for v1: (n-1) choices of vertices are available.{excluding v1
therefore n-1}
for v2:(n-2)
.
.
.
.
for vn-1:1
for vn:zero
total edges:n+(n-1)+(n-2)+...+1+0={n(n+1)}/2=0.5{n^2+n}
since we are talking of Big Oh only term with max degree will make difference
Hence, it is O(n^2) where n is no. of vertices