1
$\begingroup$

If a graph $G$ has no isolated vertices and no even cycle, then every block of $G$ is an edge of cycle.

I am trying to understand the following proof of this fact:

  1. A block with 2 vertices is an edge. (Got it)
  2. A block $H$ with more than 2 vertices is 2-connected; and thus has an ear decomposition. (Got it)
  3. If $H$ is not a single cycle, then the addition of the first ear to the first cycle creates a subgraph in which a pair of vertices is connected by 3 pairwise internally-disjoint subgraphs. (Don't understand.)
  4. By the pigeonhole principle, two of the paths have length of same parity. (Don't understand. Why does the pigeonhole principle tell us that two of the paths have the same parity?)
  5. Thus their union is even. So H must be a single cycle. (I'll understand once I understand premises 3,4.)
$\endgroup$

1 Answer 1

1
$\begingroup$

(3) If $H$ is not a single cycle then it has an ear decomposition $C_1,C_2,\ldots$. Here $C_1$ is just a cycle, and $C_2$ is a path connecting some vertex $x \in C_1$ to some other vertex $y \in C_1$ without intersecting $C_1$ in any other way. Can you see 3 pairwise internally-disjoint paths connecting $x$ and $y$? (Try drawing the situation.)

(4) Suppose the three disjoint paths connecting $x$ to $y$ are $P_1,P_2,P_3$ with lengths $\ell_1,\ell_2,\ell_3$. I claim that either at least two of $\ell_1,\ell_2,\ell_3$ are even, or at least two of $\ell_1,\ell_2,\ell_3$ are odd. Try to figure out why, and then see if you can understand why this is an application of the pigeonhole principle.

(5) You don't need to understand premises (3),(4) to understand this. From (4) you get two internally disjoint paths connecting $x$ and $y$, say $P_i,P_j$, whose lengths have the same parity. Together they form a cycle with an even number of edges (why?), contradicting the assumption.

$\endgroup$
1
  • $\begingroup$ okay, I figured out (3). Actually, I was thinking about the wrong problem for (3). For 4, not a clue. What are the pigeons and what are the holes? $\endgroup$
    – larry
    Oct 14, 2014 at 2:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .