Let $G$ be an even graph. Show that $c(G-v)\leq \frac{d(v)}{2}$, $\forall v \in V(G)$.

Where $c(G)$ is the number of connected components of $G$ and $d(v)$ is the degree of $v$.

If $G$ is even then there is an Euler tour in $G$. Hence, any edge in $G$ must be contained in a cycle, and because of that cannot be cut edge.

I know that $G$ still may hold cut vertexes, but what can I say about them ? I know that since $v$ is in an Euler tour then there are $2$ edges inciding in $v$ for each cycle that contains it. So, $G-v$ has $2d(v)$ less edges than $G$, but only $d(v)$ connected components. I.e. you have to remove two edges before disconnecting a cycle. Is that a proof?


You don't say it, but it is required that $G$ is connected.

The Euler circuit is the key to your proof. Take an example of an Euler circuit in $G$ starting at $v$, and this trail revisits $v$ exactly $d(v)/2$ times (including the terminal visit). Thus removing $v$ breaks that trail into $d(v)/2$ trails, each of which must be confined to a connected component.

  • $\begingroup$ Is an Euler circuit the same as an Euler tour? $\endgroup$ Nov 28 '17 at 18:05
  • $\begingroup$ A circuit starts and ends at the same node, otherwise yes. A connected even graph (all vertices are of even degree) always has such a circuit. $\endgroup$
    – Joffan
    Nov 28 '17 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.