A connected Eulerian graph G has 3 vertices and 5 edges Show

A connected Eulerian graph G has 3 vertices and 5 edges. Show that if one vertex has degree 4, then another vertex must have degree 2.

Solution

Sum of degrees = twice the number of edges

So sum of degrees =2*5

Let other two vertices have degree x,y

So, 4+x+y=10

x+y=6

Graph is Eulerian and connected so each vertex must have degree at least 2

Now we know that if a graph has any vertex of odd degree then it cannot have an Eulerian circuit

So, the only possible solution to x+y=6 is

x=2,y=4 or

x=4,y=2

Hence proved

A connected Eulerian graph G has 3 vertices and 5 edges. Show that if one vertex has degree 4, then another vertex must have degree 2.SolutionSum of degrees = t

Get Help Now

Submit a Take Down Notice

Tutor
Tutor: Dr Jack
Most rated tutor on our site