Exercise · ZW-BIPARTITE-GRAPH-002 · ★☆☆ Basic
How many edges does the complete bipartite graph \(K_{2,5}\) have, where each vertex of one part is joined to every vertex of the other?
Choose one option.
Show answer
- B. 10
Explanation
Each of the 2 vertices in one part is joined to the 5 in the other: \(2\cdot 5=10\). Adding (7) confuses edges with vertices.
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-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…
- ZW-BIPARTITE-GRAPH-009 A graph on 7 vertices has three connected components: two isolated edges and a path on 3 vertices.…