GATE CSE 2004 | Question: 81

Question

Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$  is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$

• 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 $G_1$ and $G_2$

Comments

G1∩G2=(V,E1∩E2)  is not a connected graph,

wht does it mean

---

Why we are not taking directed graph here? Will there also be a cycle then?

---

Proof G1 U G2 has cycle

credits:- https://stackoverflow.com/a/50458578
 

Answer 1

Question is indirectly saying in $G_1$ U $G_2$ we have edge disjoin path between some vertices because  $G_1$ ∩  $G_2$ is disconnected (means at least two vertices could reach each other via edge disjoint path ). So option (B) is True in all the cases.

Answer 2

As G1 and G2 are connected, let us say one vertex is V,now there is a way from V to all other vertices in both G1 and G2,but as their intersection  is disconnected,means there are some edges which are in G1 but not in G2 and vice versa.Or we can say there is atleast one from V to V' which is different in both G1 and G2 because if for all vertices it is same path from V to all other vertices then it will not give disconnected graph as intersection.

Now whn union will be done then their will be two paths from V to V' (one of G and other of G1) and then it will form a cycle.

Answer 3

Option B is correct.

In this example above there is cut vertex E is present so option A is false,

there is no cut edge so option C is false and

not necessarily chromatic number will be greater, it can be equal.  so option D is also false.

Answer 4

 

This can also be a approach to the solution.

Comments

Just that handwriting is not good :p