The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+22 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)$

- cannot have a cut vertex
- must have a cycle
- must have a cut-edge (bridge)
- Has chromatic number strictly greater than those of $G_1$ and $G_2$

+21 votes

Best answer

There are two connected graphs G1 and G2, with same vertices. In least case both graphs will have n-1 edges with n vertices as both the given graphs are connected.

When we UNION both the graphs as G= G1 U G2 then G will be having at most (2n-2) edges in the best case when both the graphs don't have any common edges between them (or) at least more than n-1 edges if they have few common edges between them as the intersection of these two graphs is not connected.

Suppose if both the graphs G1 and G2 have exactly the same edges then their intersection will be a connected graph.

**A graph with n vertices and more than n-1 edges will definitely have a cycle.**

**Hence (B) is the correct option!**

If in G1 has** n-1** edges, and G2 has** n-1** edges (both are connected)

then their intersection will have max **n-2** edges to be disconnected.

so G1 union G2 will have **(2n-2)-(n-2)=n** edges, so the cycle is definitely present there.

+25 votes

Take a tree for example

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

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.

+13 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.)

+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.

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.

+1 vote

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.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,271 comments

38,803 users