Let $G$ a connected graph. If every vertex of $G$ has even degree, then for any vertex $v\in V(G)$, $$\omega(G-v)\le\dfrac{\delta(v)}{2}$$ Where, $\delta(v)$ denote degree of $v$ and $\omega(G-v)$ is the number of connected components of $G-v$.
I am looking for a way to obtain that inequality, but I still have no results.
I consider two cases:
- $v$ is not a cut vertex. In this case the result is satisfied.
- $v$ is a cut vertex. In this case I have no idea
Let $v \in V(G)$. Since every vertex of $G$ has even degree, $G$ is Eulerian, i.e. $G$ has an Euler cycle $C$. We can say $C$ starts (and thus ends) at $v$. Starting at $v$, we travel a sequence of vertices, say $A_1$, along $C$, and must eventually reach $v$ once more. This occurs $\delta(v)/2$ many times (why?). This gives us $A_1,A_2,\dots, A_{\delta(v)/2}$, where $(G-v)[A_i]$ is a connected component of $G-v$. If the $A_i$ are pairwise disjoint, then we achieve equality, i.e. $\omega(G-v) = \frac{\delta(v)}{2}$. An example of this is a number of cycles joined at the same vertex such as the Friendship Graph. Otherwise, the inequality is strict (why?).
I've left out some detail, but this is the gist of it. Note by $G[A]$ we mean the subgraph of $G$ induced by the vertex subset $A$.