edited by
13,895 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

Best answer
71 votes
71 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
8 votes
8 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
3 votes
3 votes

d is the correct answer

Answer:

Related questions

58 votes
58 votes
7 answers
1
Ishrat Jahan asked Oct 27, 2014
51,884 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$...