Let G be a connected graph where all vertices have even degree. Show that for each vertex v in G, c (G \ v) ≤ δ (v) / 2. c is the number of components

Question

c is the number of connected components.

Me and a friend were trying to prove this problem, but the observations we made, we sent them to our teacher and said that they not really true.

• We thought that if v has the maximun degree then c(G\v) > 1

• if v hasn't maximun degree then c(G \ v) = 1

Which is not true

So our teacher told to see the number of vertices of odd degree as a hint .

But we still don't get the idea.

Any help? We don't count the graphs with vertices of 0 degree.

I think it has to be something with Eulerian graphs since the degree of all vertices is even...

Answer 1

When you remove $v$ from $G$, each of $v$'s neighbors is left with odd degree, and no other vertices have odd degree. But the sum of the degrees of all vertices in any connected component is even (because it's twice the number of edges in that component), so each resulting component must contain at least two of $v$'s neighbors.