Раскраска двудольного графа

[Alexander__]

Верно ли:

у любого конечного графа вершины можно раскрасить в два цвета, чтобы доля
рёбер с концами разных цветов по отношению ко всем рёбрам составляла:
- не менее 50%
- не менее 51%

Даже не знаю с чего начать решение. Подскажите?

[mihaild]

Порисуйте разные небольшие графы, посмотрите на раскраски.