Libre de triangulos 2 - Foro fmat.cl

Libre de triangulos 2

Opciones

snw Ver Perfil del Miembro Ver los mensajes de este miembro	Apr 5 2017, 03:00 PM Publicado: #1
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 2.139 Registrado: 11-June 08 Desde: UK Miembro Nº: 26.837 Nacionalidad: Colegio/Liceo: Universidad: Sexo:	$TEX: Un grafo $G=(V,E)$ se dice bipartito si es posible particionar $V=A\cup B$ de modo que $E(A,B)=E$, es decir, que los arcos de $G$ sean exactamente los arcos entre $A$ y $B$. Muestre que si $G$ no es bipartito y $e(G)\ge \frac{(n-1)^2}{4}+1$, entonces $G$ contiene un triangulo como subgrafo.$ -------------------- blep