Ejercicio · ZW-GRAFO-BIPARTITO-010 · ★★★ Avanzado
¿Puede un grafo con 9 vértices y 21 aristas ser bipartito?
Elige una opción.
Ver respuesta
- B. No: un bipartito con 9 vértices tiene a lo más 20 aristas
Explicación
Con partes \(a\) y \(9-a\) caben \(a(9-a)\le 4\cdot5=20\) aristas, así que 21 es imposible. \(K_{4,5}\) tiene exactamente 20.
Repasa el concepto: Grafo bipartito
Un grafo bipartito es un grafo \(G=(V,E)\) cuyos vértices se reparten en dos conjuntos disjuntos \(A\) y \(B\) de modo que cada arista \(e\in E\) une un vértice de \(A\) con uno de \(B\).
\[V=A\cup B,\quad A\cap B=\varnothing,\quad |e\cap A|=1\ \text{ para toda } e\in E\]
Más ejercicios de grafo bipartito
- ZW-GRAFO-BIPARTITO-001 ¿Cuál de los siguientes grafos es bipartito?
- ZW-GRAFO-BIPARTITO-002 ¿Cuántas aristas tiene el grafo bipartito completo K_2,5, donde cada vértice de una parte se une co…
- ZW-GRAFO-BIPARTITO-003 ¿Cuál es el máximo número de aristas de un grafo bipartito con 6 vértices?
- ZW-GRAFO-BIPARTITO-004 ¿Cuál de estas condiciones garantiza que un grafo NO es bipartito?
- ZW-GRAFO-BIPARTITO-005 Un grafo tiene vértices 1,dots,6 y aristas \1,4\,\1,5\,\2,4\,\2,6\,\3,5\,\3,6\. ¿Cuál es una partic…
- ZW-GRAFO-BIPARTITO-006 Al ciclo C_6, con vértices 1,dots,6 y aristas \i,i+1\ y \6,1\, se le agrega una arista. ¿Cuál hace…
- ZW-GRAFO-BIPARTITO-007 En un grafo bipartito, los 4 vértices de la parte A tienen grado 3 y los 6 vértices de B tienen tod…
- ZW-GRAFO-BIPARTITO-008 Un grafo bipartito conexo tiene partes de 3 y 5 vértices. ¿Cuál es el mínimo número de aristas que…