Question about "growing layers of a planar graphs"

35 Views Asked by At

Given a planar graph $G$ k nodes $S$ of $G$ construct "layers" $L_i$ for $i=0,1,...$ as follows $L_0=S$, having constructed layers $L_0,L_1,..,L_i$ layer $L_{i+1}$ consists of those nodes of $G \backslash (L_0 \cup L_1 \cup .. \cup L_i ) $ which have two neighbours in $L_0 \cup L_1 \cup .. \cup L_i $
Suppose that every vertex of $L_{i+1}$ has a distinct pair of two neighbours in $L_0 \cup L_1 \cup .. \cup L_i$

How large can the layer $L_i$ be?