Let G1 = (V, E1) and G2 = (V, E2) be connected graphs on the same vertex set V…
2004
Let G1 = (V, E1) and G2 = (V, E2) be connected graphs on the same vertex set V with more than two vertices. If G1 ∩ G2 = (V, E1 ∩ E2) is not a connected graph, then the graph G1 U G2 = (V, E1 U E2)
- A.
cannot have a cut vertex
- B.
must have a cycle
- C.
must have a cut-edge (bridge)
- D.
has chromatic number strictly greater than those of G1 and G2
Attempted by 79 students.
Show answer & explanation
Correct answer: B
Answer: the union must have a cycle.
Reason:
Pick two vertices x and y that lie in different connected components of the intersection (these exist because the intersection is not connected).
Because G1 is connected, there is a path P1 from x to y contained in G1. Because G2 is connected, there is a path P2 from x to y contained in G2.
Since x and y are in different components of the intersection, at least one edge of P1 is not in the intersection and at least one edge of P2 is not in the intersection; in particular P1 and P2 cannot be identical as subgraphs of the intersection.
Concatenating P1 with the reverse of P2 gives a closed walk in the union. Any closed walk contains a cycle, so the union graph contains a cycle.
Thus G1 ∪ G2 must have a cycle.