edited by
11,659 views
55 votes
55 votes

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)$

  1. cannot have a cut vertex
  2. must have a cycle
  3. must have a cut-edge (bridge)
  4. has chromatic number strictly greater than those of $G_1$ and $G_2$
edited by

11 Answers

Best answer
69 votes
69 votes

Take a tree for example 

  1. False. Every vertex of tree (other than leaves) is a cut vertex.
  2. True.
  3. False. There is no cut-edge (an edge whose removal increases the number of connected components in  graph) in $G_1 \cup G_2.$
  4. False. $G_1 \cup G_2$, $G_1$ and $G_2-$ all three graphs have same the chromatic number of $2$. 

Now, we have given counter examples for options A,C and D. So, option B is the only possible answer and its proof is given at end.

Correct Answer: Option B


We are given that $G_1$ and $G_2$ are connected. So, if we take any two vertices say $v_i$ and $v_j$ there must be path between them in both $G_1$ and $G_2.$ Now, it is given that $G_1\cap G_2$ is disconnected. That is, we have at least two vertices $v_1$ and $v_2$ such that there is no path between them in $G_1 \cap G_2.$

This means the path between $v_1$ and $v_2$ in $G_1$ and $G_2$ are distinct

When we have two distinct paths between a pair of vertices in a graph, it forms a cycle.

selected by
43 votes
43 votes

Say G1 is Black colored graph, and G2 is red colored graph.
In this figure i overlapped both graphs, to see them together.


Given that $G_1 \cap G_2 $ is Disconnected, To make it happen G1 and G2 has to meet somewhere and then leave at some point, Once they leave each other and then have to meet somewhere again to have atleast two different disconnected component.
Now it is clear that this will form a cycle (See image has cycle.)

Note: If  $G_1 \cap G_2 $ need not to be disconnected then $G_1\cup G_2 $ need not to have a cycle.

(in this case when one of the Graph has cycles then only $G_1\cup G_2$ can have cycle.)

13 votes
13 votes
A very simple reasoning in this question may fetch the answer very fast. Since the two graphs G1 and G2 are connected, there will be path from a vertex to every other vertex in  both G1 and G2 but since G1 ∩ G2 is not connected , at least for one vertex pair v1,v2 the connecting paths must be different in both G1 and G2. Hence G1 union G2 will definitely have a cycle.
6 votes
6 votes

There would be "at least " one cycle there in G1 Union G2

Answer:

Related questions

47 votes
47 votes
7 answers
1
Kathleen asked Sep 18, 2014
17,290 views
The recurrence equation$ T(1) = 1$$T(n) = 2T(n-1) + n, n \geq 2$evaluates to$2^{n+1} - n - 2$$2^n - n$$2^{n+1} - 2n - 2$$2^n + n $
31 votes
31 votes
6 answers
2
Kathleen asked Sep 18, 2014
19,268 views
The time complexity of the following C function is (assume $n 0$)int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }$O(n)$$...