Dado un grafo G es fácil ver que tenemos una partición de $V=V_1 \cup V_2$, de modo que $$e(G[V_1])+e(G[V_2])\leq e(G)/2$$. How can we improve this result showing that we can choose $V_i$ such that $e(G[V_i])\leq e(G)/3$ for $i=1,2.$
Respuesta
¿Demasiados anuncios?
Deje $V_1,V_2$ ser un desdoblamiento de $V$ que maximiza el número de $t$ de los bordes entre $V_1$$V_2$. Para un vértice $v$ definir la interna grado $d_i(v)$ como el grado de $v$ en su partita conjunto y el externo grado $d_e(v)$ como el grado de $v$ a los otros partita conjunto. Claramente $d(v)=d_i(v)+d_e(v)$.
Tenemos $d_i(v)\leq d_e(v)$: de hecho, si $d_i(v)>d_e(v)$ podemos mover $v$ a los demás partita establecer y obtener un desdoblamiento de $V$ con más aristas entre la partita conjuntos. Contradicción.
También tenga en cuenta que $e(G[V_1])+e(G[V_2])+t=e(G)$ (*).
La única cosa que queda por hacer es contar los bordes. Podemos suponer $e(G[V_1])\leq e(G[V_2])$. A continuación,$e(G[V_1])\leq e(G[V_2])=\frac12\sum_{v\in V_2}d_i(v)\leq\frac12\sum_{v\in V_2}d_e(v)=\frac12 t$.
Ahora suponiendo que $e(G[V_2])>\frac13e(G)$ implicaría que $t>\frac23e(G)$, contradiciendo (*).
Llegamos a la conclusión de que $e(G[V_1])\leq e(G[V_2])\leq\frac13e(G)$.
