1
$\begingroup$

This is a question from Bondy & Murty book, 4.1.3.

The question asks to show that every block of an eulerian graph is eulerian.

I have been stuck for a while now. The hint in the book says to use the fact that for each vertex $v$ of $G$, every cycle through $v$ is contained in some block of $G$. I do not see how one can utilize this.

$\endgroup$
1
$\begingroup$

If your edition of B&M isn't too different than mine, Problem 4.1.4 has you show that the edge set of an eulerian graph can be partitioned into cycles. You should already know that the edge set of a graph can be partitioned into blocks. The hint is to demonstrate that the cycle partition must be a refinement of the block partition. Therefore, considering the union of the cycles belonging to a given block shows that the block is also eulerian.

$\endgroup$
1
$\begingroup$

Given that a graph is eulerian if and only if each of its vertices has even degree (even graph), it is enough for us to prove that each of the blocks of a finite even graph G are even.

We will prove this by contradiction. if a block in G has an odd degree vertex, it must have at least one more odd degree vertex (the sum of all degrees must be even). any vertex of even degree in G yet odd degree in it's block must be a cut vertex in G since that's the only way for its degree to be affected by getting rid of all the vertices unrelated to its block. not only it is a cut vertex, it must also have odd degree in another block (its sum of degrees in each of its blocks must be even since it's even in G). this means that each odd vertex in a block induces another block with at least one more odd vertex which is a cut vertex inducing another block with another odd cut vertex, going to infinity. our graph is finite, which leads to a contradiction.

$\endgroup$

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.