V
V
Vladimir Petrigo2015-04-10 12:45:13
Counts
Vladimir Petrigo, 2015-04-10 12:45:13

What is the minimum value of the independence number for a bipartite graph on n vertices?

Good afternoon.
Difficulties arose with a seemingly simple question: what is the minimum value of the independence number for a bipartite graph on n vertices (for n >= 10)?
I argued that if we have a bipartite graph, then in the worst case, both subsets of vertices are equal to n/2, and therefore the minimum value of the independence number will be n/2. And a picture for my reasoning:
c1e8c7a05c354ac4b3bb465ab3e5e186.png

Answer the question

In order to leave comments, you need to log in

1 answer(s)
B
bobrovskyserg, 2015-04-10
@vpetrigo

What if n is odd?
:)

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question