edited by
13,898 views
43 votes
43 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
edited by

6 Answers

0 votes
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 votes
–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
Answer:

Related questions

58 votes
58 votes
7 answers
1
Ishrat Jahan asked Oct 27, 2014
52,016 views
What is the size of the smallest $\textsf{MIS}$ (Maximal Independent Set) of a chain of nine nodes?$5$$4$$3$$2$
34 votes
34 votes
4 answers
2
Ishrat Jahan asked Oct 27, 2014
8,185 views
What is the chromatic number of the following graph? $2$$3$$4$$5$
57 votes
57 votes
3 answers
3
34 votes
34 votes
2 answers
4
Ishrat Jahan asked Nov 2, 2014
12,927 views
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$...