Demostrar que todo gráfico $G$ con m aristas

Question

Demostrar que todo gráfico $G$ con m aristas admite una bipartición $V(G) = V1 V2$ tal que el número de aristas de $G$ cruce entre $V1$ y $V2$ es al menos $m/2$

Creo que para demostrar que en la contradicción, pero no estoy seguro de cómo ...

Answer 1

Las otras respuestas describen un enfoque algorítmico; aquí describo el enfoque probabilístico estándar.

Elija la partición al azar como sigue: con probabilidad $\frac{1}{2}$ elegimos independientemente cada vértice para que esté en $V_1$ o $V_2 = V \setminus V_1$ . La probabilidad de que una arista determinada $e$ cruces entre $V_1$ y $V_2$ es $\frac{1}{2}$ (esto se calcula observando que los puntos finales de $e$ tienen que estar en partes diferentes; si un punto final está en una parte, el otro punto final está en la otra parte con probabilidad $\frac{1}{2}$ ). Ahora calculamos el número esperado de aristas que se cruzan entre $V_1$ y $V_2$ :

$$ \mathbb{E}[e(V_1, V_2)] = \sum_{e\in E(G)} \mathbb{E}[1_e] = \sum_{e\in E(G)} P(e \in [V_1, V_2]) = \sum_{e\in E(G)} \frac{1}{2} = \frac{m}{2} $$

donde $1_e$ es la variable aleatoria indicadora de una arista $e$ cruce entre $V_1$ y $V_2$ ( $1$ si $e$ se cruza y $0$ si no lo hace). Como el número esperado de aristas en la bipartición es $\frac{m}{2}$ existe alguna bipartición con al menos este número de aristas.

Answer 2

Comience con $V_1=V(G),V_2=\emptyset$ . Proceda como sigue: para cada vértice en $V_1$ si lo mueve a $V_2$ aumenta el número de aristas entre $V_1$ y $V_2$ hazlo. De lo contrario, déjalo estar. Después de pasar por todos los vértices, esto debería producir una partición como se desea. Dejo la prueba en sí a tu criterio.

Answer 3

Empezar con una partición arbitraria $V_1,V_2$ . Ahora bien, si tenemos menos de $m/2$ bordes entre $V_1$ y $V_2$ entonces existe un vértice (supongamos que $x\in{}V_1$ ) tal que $x$ tiene más vecinos en la otra clase ( $V_2$ ) (en caso contrario, para cada vértice $v$ tendríamos al menos $deg(v)/2$ bordes entre $V_1$ y $V_2$ y por lo tanto más de $\frac{1}{4}\sum_{v\in{}|V|}deg(v)= m/2$ bordes). A continuación, establezca ${V_1}'=V_1/\{x\}$ y ${V_2}'=V_2\cup\{x\}$ . Cada vez que se hace esto se aumentan los bordes entre $V_1$ y $V_2$ por lo menos $1$ y por lo tanto el proceso termina después de un máximo de $m/2$ pasos.