Dark Mode

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
Jan 18, 2020
by Sourajit25

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 :

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

As per wikipedia,

An

unconnected graphis Eulerian in theweaker senseif 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 everyedgeof 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

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.