1

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

Brian
  • 11

1 Answers1

1

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$.

Salomo
  • 2,843
  • Would this also be a correct way of stating the answer:

    Let graph G be eulerian and have 3 vertices and have 5 edges. For all vertices that belong to V(G), d(u) is even, such that d(u) equals 0 or 2 or 4...

    I have to write it in set notation but I'm lost on how to write the rest.

     – Brian Apr 13 '15 at 16:16
  • Take $d_1=4$, then $d_2+d_3=6$, the only possibility is that one is $2$ and another one $4$. – Salomo Apr 13 '15 at 16:44
  • I understand what you're saying. How would I write that in set notation though? – Brian Apr 13 '15 at 17:52
  • You want to which extent in set notation?... – Salomo Apr 13 '15 at 20:24