Exercise · ZW-BIPARTITE-GRAPH-010 · ★★★ Advanced
Can a graph with 9 vertices and 21 edges be bipartite?
Choose one option.
Show answer
- B. No: a bipartite graph on 9 vertices has at most 20 edges
Explanation
With parts \(a\) and \(9-a\) there is room for \(a(9-a)\le 4\cdot5=20\) edges, so 21 is impossible. \(K_{4,5}\) has exactly 20.
Review the concept: Bipartite graph
A bipartite graph is a graph \(G=(V,E)\) whose vertices split into two disjoint sets \(A\) and \(B\) so that every edge \(e\in E\) joins a vertex of \(A\) to one of \(B\).
\[V=A\cup B,\quad A\cap B=\varnothing,\quad |e\cap A|=1\ \text{ for every } e\in E\]
More practice problems: bipartite graph
- ZW-BIPARTITE-GRAPH-001 Which of the following graphs is bipartite?
- ZW-BIPARTITE-GRAPH-002 How many edges does the complete bipartite graph K_2,5 have, where each vertex of one part is joine…
- ZW-BIPARTITE-GRAPH-003 What is the maximum number of edges in a bipartite graph with 6 vertices?
- ZW-BIPARTITE-GRAPH-004 Which of these conditions guarantees that a graph is NOT bipartite?
- ZW-BIPARTITE-GRAPH-005 A graph has vertices 1,dots,6 and edges \1,4\,\1,5\,\2,4\,\2,6\,\3,5\,\3,6\. Which is a valid parti…
- ZW-BIPARTITE-GRAPH-006 To the cycle C_6, with vertices 1,dots,6 and edges \i,i+1\ and \6,1\, one edge is added. Which one…
- ZW-BIPARTITE-GRAPH-007 In a bipartite graph, the 4 vertices of part A all have degree 3 and the 6 vertices of B all have t…
- ZW-BIPARTITE-GRAPH-008 A connected bipartite graph has parts of 3 and 5 vertices. What is the minimum number of edges it c…