## Graph theory: Prove min degree(G_n) >= k

Given: G is a simple (no loops or multiple edges) graph with n vertices.
The number of edges in G is at least $n(k-1)-\binom{k}{2}$, where n>k.

Prove: G has minimum degree at least k.

Proof (so far): The sum of the degrees of all the vertices in G equals twice the number of edges in G (theorem from the previous chapter of the book):
$\sum_{v \in V(G)} \deg(v) = 2 e(G) \geq 2 \left[n(k-1)-\binom{k}{2} \right] = (2n-k)(k-1)=e(K_{k-1,2n-k})$

The last term is the number of edges in a complete bipartite graph with independent sets A of size k-1 and B of size 2n-k.

Since n>k, 2n-k>2k-k=k>k-1 means that set B has more vertices and thus lower degree. All the vertices in B have degree k-1, or the minimum degree of G is k-1.

So, this is probably wrong. First problem is that the wrong result. Second, who says that G is a bipartite graph? Couldn't a graph of this many edges be of another form with lower minimum degree?

Also, who says that just because the sum of the degrees comes out to a number which looks like the number of edges in a specific type of graph that it means the graph is in that shape (yes, I did this on my own, so far, but wondering about my reasoning).

So, graph experts, where did I go wrong?
Thanks,
J