30 years ago, Yves Colin de Verdière introduced the algebraic graph invariant $\mu(G)$ for any undirected graph $G$, see [1]. It was motivated by the study of the second eigenvalue of certain Schrödinger operators [2,3]. It is defined in purely algebraic terms as the *maximum corank* in a set of generalized Laplacian matrices of $G$.


It turned out to be very powerful concept, linking algebraic with topological graph theory (and, by conjecture, with graph coloring). For example,


1. **Four Color Theorem:** Colin de Verdière conjectures $\chi(G)\leq\mu(G)+1$ where $\chi(G)$ is the chromatic number of $G$, see [4]. If true, this would prove the Four Color Theorem.
2. **Graph minor monotone:** The property $\mu(G)\leq k$ is closed under taking graph minors of $G$, meaning $\mu(g)\leq \mu(G)$ if $g$ is a minor of $G$, see [1]. So, by the Robertson–Seymour Graph Minor Theorem, the property $\mu(G)\leq k$ can be characterized by a finite number of excluded graph minors.
3. **Embeddability:** $\mu(G)$ characterizes this topological property for several families of graphs: embeddable in a line $(\mu\leq1)$, outerplanar $(\mu\leq2)$, planar $(\mu\leq3)$, or linklessly i.e. flat embeddable in ${\mathbb R}^3$ $(\mu\leq4)$, see [1,2].
4. **Embeddings in more general surfaces:** If $G$ embeds in the real projective plane or in the Klein bottle, then $\mu\leq5$. If it embeds in the torus, $\mu\leq6$. If it embeds in a surface $S$ with negative Euler characteristic $\psi$, then $\mu\leq 4−2\psi$, see [4]


Now, I have two questions, the first one being the main one:



> 
> **MAIN QUESTION:** Is someone aware of further embeddability characterizations based on $\mu(G)$ beyond the results in bullet point No. 3? In No. 3, we have full characterizations, while the results in No. 4 are just implications for $\mu(G)$ in case $G$ can be embedded, i.e. just in one direction.
> 
> 
> 



> 
> Quoting [3]: *"The parameter was motivated by the study of the maximum
> multiplicity of the second eigenvalue of certain Schrödinger operators. These operators
> are defined on Riemann surfaces. It turned out that in this study one can approximate
> the surface by a sufficiently densely embedded graph $G$, in such a way that $\mu(G)$ is the
> maximum multiplicity of the second eigenvalue of the operator, or a lower bound to it."*  
> 
> **SECOND QUESTION:** So it appears $\mu(G)$ was developed to resolve a problem in Schrödinger operator theory. I wondered when/how the idea emerged to study $\mu(G)$ as a graph invariant in its own right? I looked at [1] and [CV 1] but could not find an answer.
> 
> 
> 


References  

[1] Yves Colin de Verdiere (1990): Sur un nouvel invariant des graphes et un critère de planarité, J. Combin. Th. (B) 50, 11–21.  

[2] L. Lovasz & A. Schrijver (1998): A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc. Amer. Math. Soc. 126, 1275–1285.  

[3] H. van der Holst, L. Lovasz & A. Schrijver (1999): The Colin de Verdière graph parameter, pp. 29–
85 in: Graph Theory and Combinatorial Biology (L. Lovasz et al., eds.), János Bolyai Math.
Soc., Budapest.  

[4] Andries E. Brouwer, Willem H. Haemers (2011): Spectra of graphs, Springer Monograph.


Earlier work that Colin de Verdière cites in his article [1]:  

[CV 1] Y. COLIN DE VERDIÈRE, Spectres de variétés riemanniennes et spectres de graphes, Proc. Intern. Congress of Math., Berkeley 1986, 522-530.  

[CV 2] Y. COLIN DE VERDIÈRE, Sur la multiplicité de la premiere valeur propre non nulle du laplacien, Comment. Math. Helv. 61 (1986), 254-270.  

[CV 3] Y. COLIN DE VERDIÈRE, Sur une hypothèse de transversalité d’Arnold, Comment. Math. Helv. 63 (1988). 184-193.  

[CV 4] Y. COLIN DE VERDIÈRE, Constructions de laplaciens dont une partie finie du spectre est donné, Ann. Sci. École Norm. Sup. 20 (1987), 599-615.


<https://en.wikipedia.org/wiki/Colin_de_Verdi%C3%A8re_graph_invariant>



Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?
Embeddability in any surface but the sphere (or plane) can probably not be characterized via the Colin de Verdière number.


Suppose that $K\_n$ is the largest complete graph that embedds into a surface $S$.
This shows that the best we can hope for is "$G$ embedds in $S$ $\Leftrightarrow$ $\mu(G)\le\mu(K\_n)= n-1$".


The following is still a bit hand-wavy (maybe someone can help):
I can imagine, that a disjoint union of sufficiently many $K\_n$ can no longer be embedded into $S$ (except if $S$ is a sphere/plane). My intuition is that any additional $K\_n$ must embedd in one of the regions given by the embedding of the previous $K\_n$, and this region is probably "of a lesser genus" (if the genus is not already 0).
For example, this is true for $S$ being the projective plane: $K\_5$ embedds in $\Bbb R P^2$, but $K\_5+K\_5$ does not (see [here](https://mathoverflow.net/q/368975/108884)).
Also, a claim in [this question](https://mathoverflow.net/q/244029/108884) seems to support this in the orientable case.


But we also have $\mu(K\_n+\cdots +K\_n)=\mu(K\_n)=n-1$ (see [1]), contradicting the desired characterization.




---


[1] van der Holst, Lovász, Schrijver:
["The Colin de Verdière graph parameter"](https://homepages.cwi.nl/%7Elex/files/cdvsurvey_new2.pdf), Theorem 2.5


