I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand:
A crown of a graph $G = (V,E)$ consists of $H\subseteq V$ and $I \subseteq V$ with $H \cap I = \varnothing$ s.t. the following three conditions hold:
- $H = N(I)$
- $I$ forms an independent set
- the edges connecting $H$ and $I$ contain a matching in which all elements of $H$ are matched.
$N(I)$ is the neighborhood of vertices $I$, i.e., $N(I) = \{u \mid v \in I \land (u,v) \in E\}$.
I'm stuck with the third point: I'm interpreting it as "in the bipartite graph $(H, I, F)$ with $F = \{(u,v) \in E \mid u\in I \land v \in H\}$ there is a matching $M\subseteq F$ s.t. $\forall v \in H: \exists (u,v) \in F$, i.e., each vertex in $H$ is covered by an edge in the matching $M$".
But does this not imply that $|I| \geq |H|$ since there can at most be $|I|$ non-adjacent edges connected to vertices in $I$? This would imply that $I$ is a set of vertices that have degree 1, which surely is not the intention since a crown is intended to be a generalization of 1-connected vertices.
What am I missing?
