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

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

Solution

if graph G bee a bipartite graph has parts of size m and n, it has at most mn edges.

the possibilities if m+n=17 is:

In particular, such a large (73) not in this mn list so it cannot be bipartite.