# GATE CSE 2004 | Question: 81

5.7k views

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
9
Refere http://math.stackexchange.com/questions/1535029/union-of-two-graphs This question, if you are not able to interpret this image.
1
0
I am not getting what he is trying to say. Can you explain a bit?
0
https://www.gatementor.com/viewtopic.php?f=260&t=8394

This explains it in a simple way.....
0

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

wht does it mean

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

### 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

ago

## Related questions

1
5.4k views
Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? $P,Q,R,S,T,U$ $P,Q,R,U,S,T$ $P,Q,R,U,T,S$ $P,Q,T,R,U,S$
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$
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)$ $O(n \log n)$ $O(n^2)$ $O(2^n)$
Let $A[1,\ldots,n]$ be an array storing a bit ($1$ or $0$) at each location, and $f(m)$ is a function whose time complexity is $\Theta(m)$. Consider the following program fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if a[i] == 1) counter++; ... 0;} } The complexity of this program fragment is $\Omega(n^2)$ $\Omega (n\log n) \text{ and } O(n^2)$ $\Theta(n)$ $o(n)$