coding instance. From the proof of Proposition \[prop:tall\] and Lemma \[delta\_s-cycle\], the following observation is given.

The optimal index codelength of the corresponding index coding instance is larger than or equal to $|E|$. \[ob:codelength\]

At this point, we prove validity of this model and the equivalence between an NCLE and an ICSIE. In order to show that they are equivalent, the following lemma is needed.

In the equivalent $(\bm{\delta}_s,\mathcal{G})$-ICSIE for a given network coding instance, there is a unique $\bold{\hat{X}}_E$ such that $\hat{F}(\bold{\hat{X}}_S,\bold{\hat{X}}_E)=\bm{\sigma}$ for any codeword $\bm{\sigma}\in\mathbb{F}_q^{|E|}$ and $\bold{\hat{X}}_S$.

From Proposition \[prop:condition\], there is no cycle in a subgraph which consists of the set of receivers $\{R_e | e\in E\}$ and the set of messages $\{\hat{X}_e | e\in E\}$. Thus, $N_{\rm{opt}}^q(\bm{\delta}_s,\mathcal{G})\geq |E|$ and we assume that a $(\bm{\delta}_s,\mathcal{G})$-ICSIE with codelength $|E|$ exists. Since different symbols of $\bold{\hat{X}}_E$ for given $\bold{\hat{X}}_S$ result in different codewords and the codelength is $|E|$ by Lemma \[delta\_s-cycle\], there exists unique $\bold{\hat{X}}_E$ such that $\hat{F}(\bold{\hat{X}}_S,\bold{\hat{X}}_E)=\bm{\sigma}$ for the above conditions.

\[lemma:existence\]

Next, the equivalence between an NCLE and an ICSIE for a given network coding instance is shown in the following theorem.

For a given network coding instance, a $(\bm{\delta},\mathbb{G})$-NCLE exists if and only if the corresponding 