Exercise · ZW-BIPARTITE-GRAPH-008 · ★★☆ Intermediate
A connected bipartite graph has parts of 3 and 5 vertices. What is the minimum number of edges it can have?
Choose one option.
Show answer
- B. 7
Explanation
A connected graph on 8 vertices needs at least \(8-1=7\) edges, and a bipartite tree with parts of 3 and 5 vertices attains it.
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-009 A graph on 7 vertices has three connected components: two isolated edges and a path on 3 vertices.…