Consider the graph given below: The two distinct set of vertices, which make…
2015
Consider the graph given below:
The two distinct set of vertices, which make the graph bipartite are
- A.
\((v_1, v_4, v_6); (v_2, v_3, v_5, v_7, v_8)\) - B.
\((v_1, v_7, v_8); (v_2, v_3, v_5, v_6)\) - C.
\((v_1, v_4, v_6, v_7); (v_2, v_3, v_5, v_8)\) - D.
\((v_1, v_4, v_6, v_7, v_8); (v_2, v_3, v_5)\)
Attempted by 149 students.
Show answer & explanation
Correct answer: C
Definition: A graph is bipartite if its vertices can be split into two sets so that every edge joins a vertex in one set to a vertex in the other set.
Place v1 in the first set.
Neighbors of v1 are v2, v3 and v5, so those must go to the second set.
Neighbors of v2 are v1, v4 and v6. Since v1 is in the first set, v4 and v6 must be placed in the first set as well.
Neighbors of v3 are v1, v4 and v7. With v1 and v4 in the first set, v7 must also be in the first set.
Vertex v5 is adjacent to v1, v6 and v7, all of which are in the first set, so v5 remains in the second set.
Vertex v8 is adjacent to v4, v6 and v7 (all in the first set), so v8 belongs to the second set.
Final bipartition:
{v1, v4, v6, v7}
{v2, v3, v5, v8}
Check: every edge (outer edges and inner square edges, and the diagonals connecting outer corners to inner corners) connects a vertex from the first set to a vertex from the second set, so the graph is bipartite with the sets above.
A video solution is available for this question — log in and enroll to watch it.