A bipartite graph has nodes ai and bi for i = 0, 1,…, 5. There is an edge betwee
ID: 3669799 • Letter: A
Question
A bipartite graph has nodes ai and bi for i = 0, 1,…, 5. There is an edge between ai and bi if i-j is divisible by 2 or 3. For example, a0 is connected to b0, b2, b3, and b4. Also, a3 is connected to b0, b1, b3, and b5. Another way to understand this graph is to realize that ai is connected to bj unless j = i+i or j = i-1, where arithmetic is modulo 6. Say a complete bipartite subgraph is maximal if no nodes can be added to it and the “complete” property be maintained. Which of the following instances of K2,2 is NOT maximal?
a. {a2, a5, b2, b5}
b. {a0, a3, b0, b3}
c. {a1, a3, b3, b5}
d. {a2, a3, b0, b5}
Explanation / Answer
Explanation:
Jump on to the final choice of d. {a2, a3, b0, b5}