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.

  • 1
    $\begingroup$ 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.$ $\endgroup$ – bof Oct 23 '15 at 1:24

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?

  • $\begingroup$ 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? $\endgroup$ – D.Peterson Nov 3 '15 at 20:12
  • $\begingroup$ A bipartite graph with 17 vertices can have at most 72 edges. Since the graph has 73 edges, it cannot be bipartite. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.