Exercise · ZW-BIPARTITE-GRAPH-005 · ★☆☆ Basic

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 partition \(A\), \(B\)?

Choose one option.

Show answer
  • C. \(A=\{1,2,3\}\), \(B=\{4,5,6\}\)

Explanation

Every edge joins a vertex of \(\{1,2,3\}\) with one of \(\{4,5,6\}\). In the other options some edge lies inside a part, for example \(\{1,4\}\).

Study Discrete mathematics in ZWMath →

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-004 ZW-BIPARTITE-GRAPH-006 →