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

2 votes
2 votes
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.
1 votes
1 votes
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.
0 votes
0 votes

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.

0 votes
0 votes

 

This can also be a approach to the solution.

Answer:

Related questions

47 votes
47 votes
7 answers
1
Kathleen asked Sep 18, 2014
17,289 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,267 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)$$...