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

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.

• Hint: $1\times16=16,\ 2\times15=30,\ 3\times14=42,\ 4\times13=52,\ 5\times12=60,\ 6\times11=66,\ 7\times10=70,\ 8\times9=72,\ 9\times8=72,\ 10\times7=70,\ 11\times6=66,\ 12\times5=60,\ 13\times4=52,\ 14\times3=42,\ 15\times2=30,\ 16\times1=16.$ – bof Oct 23 '15 at 1:24

## 2 Answers

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?

• The largest m*n is 9*8 which is 72, clearly this is less than 73 but how to we present this in proof form? – D.Peterson Nov 3 '15 at 20:12
• A bipartite graph with 17 vertices can have at most 72 edges. Since the graph has 73 edges, it cannot be bipartite. – Michael Biro Nov 3 '15 at 22:54

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.