Eularian graph, prooving certain properties.

48 Views Asked by At

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

1

There are 1 best solutions below

4
On

Let $v_1,v_2,v_3$ be the vertices and with degrees $d_1,d_2,d_3$. As $G$ is Eulerian, $d_1,d_2,d_3$ are even integers, that is $0,2$ or $4$. If there is a vertex with degree $4$, say $d_1=4$, then since there are $5$ edges, $d_1+d_2+d_3=10$, hence some vertex must be of degree $2$.