Exercise · ZW-BIPARTITE-GRAPH-003 · ★☆☆ Basic
What is the maximum number of edges in a bipartite graph with 6 vertices?
Choose one option.
Show answer
- A. 9
Explanation
With parts of sizes \(a\) and \(6-a\) there is room for \(a(6-a)\) edges, maximal at \(a=3\): \(3\cdot3=9\). The 15 edges of \(K_6\) would include triangles.
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-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…
- ZW-BIPARTITE-GRAPH-009 A graph on 7 vertices has three connected components: two isolated edges and a path on 3 vertices.…