search
Log In
42 votes
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$
in Algorithms
edited by
5.7k views
9
Refere http://math.stackexchange.com/questions/1535029/union-of-two-graphs This question, if you are not able to interpret this image.
1
yes it is good link
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?

9 Answers

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

ago
Answer:

Related questions

27 votes
3 answers
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$
asked Sep 19, 2014 in Algorithms Kathleen 5.4k views
33 votes
8 answers
2
8.9k 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 $
asked Sep 19, 2014 in Algorithms Kathleen 8.9k views
20 votes
7 answers
3
9k 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)$ $O(n \log n)$ $O(n^2)$ $O(2^n)$
asked Sep 19, 2014 in Algorithms Kathleen 9k views
50 votes
13 answers
4
11.5k views
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)$
asked Sep 19, 2014 in Algorithms Kathleen 11.5k views
...