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

