Eigenfunctions and Nodal Domains (From Perron Frobenius to Courant's Nodal Domain Theorem)

NEW

Problem: Reconstructed statement: Let $G=(V,E)$ be a finite nonempty simple graph. A “bipartite minor” means the contraction quotient obtained from a partition of $V$ into nonempty connected bags, with two bags adjacent iff some edge of $G$ joins them. Let $G^*$ be such a bipartite contraction minor with maximum possible number of vertices. A generalized Laplacian on $G$ is a real symmetric matrix $M$ with $M_{ij}<0$ when $ij\in E$, $M_{ij}=0$ when $i\ne j$ and $ij\notin E$, and arbitrary diagonal. Weak nodal domains of an eigenfunction $u$ are the connected components of $\{u\ge0\}$ and $\{u\le0\}$; if $u$ has no zeros, these are just the positive and negative sign components.

Under this standard contraction-minor interpretation, the answer is yes.

Result: Let the bags of $G^*$ be

$$B_1,\dots,B_m,\qquad m=|V(G^*)|.$$

Since $G^*$ is bipartite, choose a proper 2-coloring

$$\varepsilon:\{B_1,\dots,B_m\}\to\{+1,-1\}.$$

Define $u:V(G)\to\mathbb R$ by

$$u(v)=\varepsilon(B_i)\quad\text{if }v\in B_i.$$

Each bag $B_i$ is connected, and no two bags of the same sign are joined by an edge of $G$, because such an edge would give an edge between same-colored vertices of $G^*$. Hence the positive and negative connected components of $u$ are exactly the bags $B_i$. Therefore $u$ has exactly

$$m=|V(G^*)|$$

weak nodal domains.

It remains to realize $u$ as an eigenfunction of a generalized Laplacian. Define $M$ by

$$M_{ij}= \begin{cases} -1,& ij\in E,\ i\ne j,\\ 0,& ij\notin E,\ i\ne j, \end{cases}$$

and choose the diagonal entries

$$M_{ii}:=\frac{\sum_{j\sim i}u(j)}{u(i)}.$$

This is well-defined because $u(i)=\pm1$. Then for every vertex $i$,

$$(Mu)_i=M_{ii}u(i)-\sum_{j\sim i}u(j) =\sum_{j\sim i}u(j)-\sum_{j\sim i}u(j)=0.$$

Thus $Mu=0$, so $u$ is a nonzero eigenfunction of the generalized Laplacian $M$.

Therefore there exists a generalized Laplacian on $G$ with an eigenfunction having exactly $|V(G^*)|$ weak nodal domains.

Citation: No external resolution is used here; the proof is the construction above. Under the ordinary graph-minor convention allowing arbitrary edge deletion, the statement would be false/trivialized, since every graph has an edgeless bipartite minor on $|V(G)|$ vertices. The paper’s wording “as defined in Thm. 3.29” supports the contraction-quotient interpretation used here.