Exercise · ZW-BIPARTITE-GRAPH-006 · ★★☆ Intermediate
To the cycle \(C_6\), with vertices \(1,\dots,6\) and edges \(\{i,i+1\}\) and \(\{6,1\}\), one edge is added. Which one makes it non-bipartite?
Choose one option.
Show answer
- D. \(\{1,3\}\)
Explanation
With \(A=\{1,3,5\}\) and \(B=\{2,4,6\}\), the edges \(\{1,4\}\), \(\{2,5\}\) and \(\{3,6\}\) join different parts. But \(\{1,3\}\) closes the triangle \(1,2,3\).
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-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.…