Given:Gis a simple (no loops or multiple edges) graph withnvertices.

The number of edges inGis at least $\displaystyle n(k-1)-\binom{k}{2}$, wheren>k.

Prove:Ghas minimum degree at leastk.

Unless I made a mistake, I have successfully proven that this is not true. Please help if you can (thank you).

Proof(so far): The sum of the degrees of all the vertices inGequals twice the number of edges inG(theorem from the previous chapter of the book):

$\displaystyle \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 setsAof sizek-1andBof size2n-k.

Sincen>k,2n-k>2k-k=k>k-1means that setBhas more vertices and thus lower degree. All the vertices inBhave degreek-1, or the minimum degree ofGisk-1.

So, this is probably wrong. First problem is that the wrong result. Second, who says thatGis 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