# Graph theory: definiton of the crown of a graph

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?

• Your definition of $N(I)$ is neither necessary nor correct. – Yixin Cao Nov 20 '14 at 14:01
• Could you please explain why? – mort Nov 20 '14 at 14:04
• $H$ is supposed to be a generalization of the cutpoint (a 1-connected vertex?), not $I$. – Yixin Cao Nov 20 '14 at 14:09

Yes, it implies that $|I| \geq |H|$ but it does not imply $I$ contains only vertices of degree 1. The edges joining $H$ to $I$ contain an H-covering matching, but there can be many more edges. See, for instance, D. Marx' slides on crown reduction: http://www.cs.bme.hu/~dmarx/papers/marx-agape09-slides-print.pdf