edited by
11,674 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

0 votes
0 votes

OPTION B

Since there are two connected graphs G1 and G2 for the same set of vertices.

Now, G1 intersection G2 is disconnected means G1 and G2 must have at least one different path between two vertices.

So, for that pair of vertex cycle is formed

0 votes
0 votes

The diagram can easily be deduced.

1st in the graphs, there will not be a single cut vertex, but multiple

2nd There will definitely be a cycle

3rd there will not be a single cut edge but multiple

4th the chromatic number of the union graph can be equal or greater than the chromatic number of the single graphs.

Hence option B is most suited

Answer:

Related questions

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