Grafo Bipartito

-------------------------------------------------
Grafo bipartito

En teoría de grafos, un grafo bipartito es un grafo G=(N,E) cuyos vértices se pueden separar en dos conjuntos disjuntos U y V, esdecir, tal que se cumple:
*
*
de manera que las aristas sólo pueden conectar vértices de un conjunto con vértices del otro; es decir:
*  no existe ninguna arista  ni 
Los grafosbipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.
Los dos conjuntos U y V pueden ser pensados como uncoloreo del grafo con dos colores: si pintamos los vértices en U de azul y los vértices deV de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otrolado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.
Un grafo bipartito con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si|U| =|V|, esto es, si los dos subconjuntos tiene la misma cantidad de elementos, decimos que el grafo bipartito G es balanceado.
-------------------------------------------------
Ejemplos
* Todo grafosin ciclos con cantidad de nodos impar es bipartito. Como consecuencia de esto:
* Todo árbol es bipartito.
* Los grafos cíclicos con un número par de vértices son bipartitos.
*Todo grafo planar donde todas las caras tienen un número par de aristas es bipartito.

-------------------------------------------------
Grafo completo

En teoría de grafos, un grafo completo esun grafo simple donde cada par de vértices está conectado por una arista.
Un grafo completo de n vértices tiene  aristas, y se nota . Es un grafo regular con todos sus vértices de grado . La única formade hacer que un grafo completo se torne disconexo a través de la eliminación de vértices, sería eliminándolos todos.
El teorema de Kuratowski dice que un grafo planar no puede contener  (ó...