Prove or disprove the following. (a) Let G be a multigraph with an Eulerian trail. If an

Problem 6

Prove or disprove the following.

(a) Let G be a multigraph with an Eulerian trail. If an edge (possibly an additional edge) is added between two odd vertices, then the resulting multigraph is Eulerian.

(b) Let G be a multigraph containing an Eulerian trail whose two odd vertices are adjacent. If the edge joining these two vertices is removed from G, then the resulting multigraph is Eulerian.

(c) Let G be a graph containing an Eulerian trail. If a new vertex is added to G and joined to all odd vertices of G, then the resulting graph is Eulerian.

                                                        Step by Step Solution

Step 1 of 3

Let G be a multigraph with an Eulerian trail.

It is known that a connected multigraph G has an Eulerian trail if and only if it has exactly two odd vertices.

Since G is a multigraph with an Eulerian trail, it has exactly two odd vertices.

If an edge is added between two odd vertices, then every vertex of G becomes even.

So, the resulting multigraph is an Eulerian.

Hence, the given statement is true.