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

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

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

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

weak nodal domains.

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

and choose the diagonal entries

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

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.