Register

GATE IT 2008 | Question: 27

• edited by
21,785 views
59 59 votes

$G$ is a simple undirected graph. Some vertices of $G$ are of odd degree. Add a node $v$ to $G$ and make it adjacent to each odd degree vertex of $G$. The resultant graph is sure to be

  1. regular
  2. complete
  3. Hamiltonian
  4. Euler

6 Answers

Best answer
90 90 votes

In any simple undirected graph, total degree of all vertices is even (since each edge contributes $2$ degrees). So number of vertices having odd degrees must be even, otherwise their sum would have been odd, making total degree also odd.

Now Single vertex $v$ is connected to all these even number of vertices (which have odd degrees). So degree of $v$ is also even. Moreover, now degree of all vertices which are connected to $v$ is increased by $1$, hence vertices which had odd degree earlier now have even degree.

So now, all vertices in graph have even degree, which is necessary and sufficient condition for euler graph. So (D) is correct.

• edited by
11 11 votes

Given : G is undirected simple directed graph & some of the vertices are odd. and add 1 vertex V in the graph and connect that vertex to all the odd degree vertices , now new Graph we have to verify : 

 please Don't Get confused with Connected or Disconnected, because we have a theorem that says :

for any disconnected or connected graph if their exist exactly 2  odd number of vertices then their must be an edge between them . so by that  we can say the number of odd degree vertices will always be even. 

now we are adding vertex V and connecting it to all the odd degree vertices that will make their degree as even.Moreover, the degree of new vertex  V will be even a/c to theorem (the number of odd degree vertices will always be even. )

so it will be Euler graph.

• edited by
0 0 votes

There is a theorem that if the graph has atmost two vertices of atmost 2 degree, then graph will have Euler path. Hence option D is correct.

–2 –2 votes
In question nothing is mentioned so it may be connected or not connected ( components >2)

if take not connected ( components=2)
one component is triangle ( regular graph with degree 2 ( even degree))
second component is 2 vertices and 1 edge ( both vetex have degree 1 ( odd degree))

now node V added to both vetex of second component so second component become regular graph with degree 2

Hence resultant graph is regular.

but this is not possible with every case .

For complete,Hamiltonian,Euler graph , graph should be connected then how these graph are possible with disconnected graph

 

Therefore if we consider graph as disconnected then no option match as answer

Plz verify this
• edited by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2008 | Quest...Next → · GATE IT 2008 | Quest...
← Previous in category · GATE IT 2008 | Quest...Next in category → · GATE IT 2007 | Quest...
Position:
Show:

Related questions

77 77 votes
9 answers 9 answers
133k
133k views
Ishrat Jahan asked Oct 27, 2014
132,836 views
GATE IT 2008 | Question: 4
What is the size of the smallest $\textsf{MIS}$ (Maximal Independent Set) of a chain of nine nodes?$5$$4$$3$$2$
46 46 votes
4 answers 4 answers
13.8k
13.8k views
Ishrat Jahan asked Oct 27, 2014
13,791 views
GATE IT 2008 | Question: 3
What is the chromatic number of the following graph? $2$$3$$4$$5$
82 82 votes
5 answers 5 answers
16.6k
16.6k views
Ishrat Jahan asked Nov 3, 2014
16,566 views
GATE IT 2005 | Question: 56
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i...
44 44 votes
2 answers 2 answers
16.3k
16.3k views
Ishrat Jahan asked Nov 2, 2014
16,270 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$...