menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

GATE2004-81

40 votes
5.3k 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.3k 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?

8 Answers

48 votes

Take a tree for example 

 

  1. False. Every vertex of tree(other than leaves) is a cut vertex.
  2. True.
  3. False. Without E in $G1$ and $G2$, $G1 \cup G2$  has no bridge.
  4. False. $G1 \cup G2$, $G1$, $G2$ three graphs have same chromatic number of $2$. 

edited by
39

G1 and G2 are connected graph. As G1 $\cap$ G2 is disconnected graph, there must exist two vertices say V1 and V2 such that there is no path between them in G1 $\cap$ G2.

But as G1 is connected graph it must have some path P1 between vertices V1 and V2. Similarly, G2 must have some path P2 between V1 and V2.

Now, these P1 and P2 are not the same paths, if they are they will be present in G1 $\cap$ G2, which will contradict with our assumption.

In G1 $\cup$ G2, we have two paths P1 and P2 to between V1 and V2. That form the cycle. See the image.

1
@srestha but G1 intersection G2 is connected but should be not connected as specified in question.

Correct me if m wrong.

edited by
1
@Prateek

See the node D, if you try to take intersection of G1 and G2, D will be disconnected as the path is not common in G1 and G2.
0

@srestha

G1 intersection G2 is disconnected or not?

I found that we have a common path in both G1 and G2 ,which is connected.

what actually G1 and G2 intersection is?

28 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.)

8 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.
5 votes

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

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

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

 

This can also be a approach to the solution.

0
Just that handwriting is not good :p
← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →
Answer:

Related questions

27 votes
3 answers
1
4.9k views
GATE2004-44
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$
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 4.9k views
33 votes
8 answers
2
8.2k views
GATE2004-84
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 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.2k views
20 votes
7 answers
3
8.3k views
GATE2004-83, ISRO2015-40
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)$
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 8.3k views
49 votes
13 answers
4
10.6k views
GATE2004-82
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) ... ;} } The complexity of this program fragment is $\Omega(n^2)$ $\Omega (n\log n) \text{ and } O(n^2)$ $\Theta(n)$ $o(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)$
asked Sep 19, 2014 in Algorithms Kathleen 10.6k views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...