Register

GATE CSE 2004 | Question: 81

• edited by
12,003 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
User Avatar

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

User Avatar
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

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

34 votes
34 votes
2 answers
10
Ishrat Jahan asked Nov 2, 2014
13,098 views
GATE IT 2004 | Question: 37
What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$? $10$ $11$ $18$ $19$
What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$?$10$$11$...
User Avatar
25 votes
25 votes
8 answers
11
Ishrat Jahan asked Nov 1, 2014
7,155 views
GATE IT 2004 | Question: 5
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices?$n-1$$n$$n+1$$2n-1$
User Avatar
37 votes
37 votes
7 answers
12
Kathleen asked Sep 18, 2014
12,912 views
GATE CSE 2004 | Question: 77
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is $2$ $3$ $4$ $5$
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is$2$$3$$4$$5$
User Avatar
Link Copied!