in Graph Theory edited by
10,945 views
39 votes
39 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
in Graph Theory edited by
10.9k views

4 Comments

Wont it be regular and complete also ? Please explain with example how
0
0

 

Vertex V is added to Graph G and made adjacent to odd degree vertices.

Resultant Graph G is not a Regular, not a Complete, not a Hamiltonian. but only Euler !!

9
9
Perfect Answer Thanks Alot
0
0
The question is weird. It should have been stated that the graph $G$ is connected. But if we assume that the graph $G$ is not connected, then either of the options can be true. So assuming the graph to be connected we get option $D$ as true.
0
0

6 Answers

67 votes
67 votes
Best answer

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

4 Comments

What's the difference then?
2
2
edited by

Every Euler Graph is Eulerian but every Eulerian Graph is not an Euler Graph.

Euler Graph : Every Graph where degree of all the vertices is even.(Not necessarily connected)

Eulerian Graph : A graph containing an Eulerian Circuit or Eulerian Cycle.Hence the necessary conditions are : 

  1. Contains a circuit that visits every edge  of the graph and starts and ends at the same vertex.
  2. All vertices have even degree(hence it is an Euler Graph) 
  3. Not Necessarily Connected.

As per wikipedia, 

An unconnected graph is Eulerian in the weaker sense if and only if each connected component has an Eulerian cycle.

 Example :

 

This is an Euler graph but not an Eulerian Graph ,because here all vertices have even degree but disjoint cycles do not visit all the edges of the graph.Hence not Eulerian

 

These are both Euler Graph and Eulerian Graph,since all vertices have even degree and every  connected component has an Eulerian Circuit.

A disconnected graph is Eulerian if:

  • There is exactly one connected component with more than one vertex and it has an Eulerian Cycle, i.e. it has a circuit that visits every edge of the graph.
  • All the other disconnected components are singletons.  


One more important concept is Eulerian Path : A Graph is said to have an Eulerian Path if there are 0 to exactly 2 vertices having odd degree. That is all graphs having all even degree vertices or exactly 2 odd degree vertices.Thus every Eulerian Graph has an Eulerian Path but not the other way round.

Source: Euler Graph Eulerian graph Eulerian Path

14
14
@ Sourajit25

What I got from your comment is given all vertices are even degree,

In Eulerian graph a single component having a Eulerian cycle and it can have isolated vertices.  

and in Euler graphs more than one component can have Eulerian Cycles.

Is this right?
1
1
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

2 Comments

The graph must be connected. 
Check this-
This is the counter-example for disconnected graph case.
 

 

1
1

@Soumya29 You are confusing between Euler and Eulerian Graph.It is not a necessary condition for Euler graph to be connected.See this.

0
0
3 votes
3 votes

d is the correct answer

1 comment

You are supposed to add a node v you have added edge I think
1
1
0 votes
0 votes
Mine is coming out to be both Euler and Hamiltonian.
Answer:

Related questions