Двухстороннее связное доказательство графа

Question

Друг представил мне гипотезу, которая кажется верной, но ни один из нас не может выдвинуть доказательства. Вот проблема:

Для связного двудольного графа с непересекающимися непустыми множествами вершин U и V, такими, что | U | <| V |, все вершины находятся либо в U, либо в V, и нет ребер, соединяющих две вершины внутри одной и той же вершины. множество, то существует хотя бы одно ребро, которое соединяет вершины a∈U и b∈V так, что степень (a)> степень (b)

Тривиально доказать, что в U есть хотя бы одна вершина со степенью выше единицы в V, но доказать, что существует пара с ребром, соединяющим их , ставит нас в тупик.

Answer 1

Для любого ребра e = (a, b) с a∈U и b∈V, пусть w (e) = 1 / deg (b) -1 / deg (a). Для любой вершины x сумма 1 / deg (x) по всем ребрам, инцидентным с x, равна 1, потому что есть deg (x) таких ребер. Следовательно, сумма w (e) по всем ребрам e равна | V | - | U |. Поскольку | V | - | U |> 0, w (e)> 0 для сом-края e = (a, b), что означает, что deg (a)> deg (b).

Answer 2

Докажите это противоречием, т.е. предположим, что deg (a) ≤ deg (b) ∀ (a, b) ∈E , где E - набор ребер графа ( с условием, что первый элемент находится в U , а второй в V ).

Для F⊆E обозначить V (F) подмножество V , которое доступно через набор ребер F , то есть:

V (F) = {b | (a, b) ∈F}

Теперь создайте набор ребер F следующим образом:

F = empty set
For a ∈ U:
    add any edge (a,b)∈E to F
Keep adding arbitrary edges (a,b)∈E to F until |V(F)| = |U|

Полученный набор V (F) связан со всеми узлами в U , следовательно, по нашему предположению, мы должны иметь

∑ _a∈U град (а) ≤ ∑ _{b∈V (F)} град (б)

Однако, поскольку | U | = | V (F) | и | U | <| V | </em>, мы знаем, что должен быть хотя бы один «недостигнутый» узел v∈V \ V (F) , и поскольку граф связан, deg (v)> 0 , поэтому мы получаем

∑ _a∈U град (а) <∑ <sub>b∈V град (б)

что невозможно; это должно быть равенство для двудольного графа.