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 the graph is bipartite one partition will have x vertices and other with have y vertices

x+y=17

Maximum number of edges in this graph is E=xy

WHen is xy maximum?

E=x(17-x)

Clearly there is a symmetry int he problem, x and y are interchangeable

SO, maximum happens at x=y

x=y=17/2=8.5

Max. number of edges =8.5^2=72.25<73

So we cannot have a bipartite graph with given number of vertices and edges