# Graph theory problem and connected components

In a connected graph $$G$$ where degree of every vertex $$v$$ is even, show that $$G\setminus v$$ has at most $$\dfrac{1}{2}\deg(v)$$ connected components.

$$G\setminus v$$ is the graph which is left after removing $$v$$ and all of its incident edges from $$G$$.

The graph $$G$$ is Eulerian. Fix any Eulerian cycle on $$G$$. It is easy to see, when we remove $$v$$ from $$G$$, the cycle will be cut into at most $$\frac 12\deg v$$ parts, each of which is connected. Since each connected component of $$G\setminus\{v\}$$ is a union of these parts, there are at most $$\frac 12\deg v$$ components.