Proof clarification from Laszlo Lovasz' Matching Theory, "A hypergraph is balanced iff it does not contain an unbalanced odd circuit.

24 Views Asked by At

From the book Laszlo Lovasz' Matching Theory, beginning from page 468 (of the book, not the pdf file), there is a theorem:

Thm 12.3.2: A hypergraph is balanced iff does not contain an unbalanced odd circuit

Previously we have defined:

The circuit is called unbalanced if $E_i \cap \{x_1,...,x_k\}=\{x_i,x_{i+1}\}, \forall 1 \leq i \leq k$

My questions are:

  1. Is an unbalanced circuit then a graph-circuit, given we restrict the hypergraph to $\{x_1,...,x_k\}$? (Restriction here means we take the sub-hypergraph)?

  2. In the last paragraph of the proof there is (below), odd here is supposed to be even, no?

    Since $G_0$ is connected .... and such a path must have odd length.

  3. Furthermore, in the same paragraph, why exactly is P a graph-path? Supposing the 2 red vertices in $E$ is $v_0,v_{2k}$, and we have the path $P=\{v_0,E_0,v_1,...,v_{2k}\}$. Why are hyperedges $E_0,...,E_{2k-1}$, when restricted to $\{v_0,...,v_{2k}\}$ forms an unbalanced path? That is, why is (for example) $E_0=\{v_0,v_1,$vertices not in P$\}$? Why can't $v_2$ be in $E_0$?