Discrete math Please write your answer neatly so that I can

Discrete math. Please write your answer neatly so that I can read it.

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

Solution

Proof:

We will use this theorem : If a bipartite graph has parts of size m and n, it has at most mn edges.

Here, m+n = 17.

So maximum possiblity will be 9 and 8 so maximum a bipartrite grph with 17 edges can have 7*8 = 72 edges.

Thus, A bipartite graph with 17 vertices can have at most 72 edges. Since the graph has 73 edges, it cannot be bipartite.