Prove that a simple graph with 17 vertices and 73 edges cannot be bipartite

Question

Prove that a simple graph with 17 vertices and 73 edges cannot be bipartite.

-I asked my professor for help on this and his hint was to break the graph up into two vertex sets and count the number of edges within each vertex set.

-We did several examples in class involving chromatic graphs that involved 6 vertices just to have basic examples, I do understand what bipartite means and how such a graph would look like although I don't understand how I would necessarily prove that the given graph isn't bipartite. Seems clear that I would use contradiction, just not sure how. Any help is appreciated.

Answer 1

If a bipartite graph has parts of size $m$ and $n$, it has at most $mn$ edges.

What are the possibilities if $m + n = 17$? In particular, how large can $mn$ be?

Answer 2

It can be found out that the maximum value of $f(n)= n(17-n)$ using calculus comes out to be $72$ which is less than $73$ i.e. the largest value of $mn$(when $m+n=17$) is $72$ and hence a simple graph on $17$ vertices and $73$ vertices cannot be bipartite.