The Graph Minor Theorem of Robertson and Seymour asserts
that any minor-closed graph property is determined by a finite set
of forbidden graph minors. It is a broad generalization e.g. of the Kuratowski-Wagner theorem, which characterizes planarity in terms of two forbidden minors: the complete graph $K\_5$ and the complete bipartite graph $K\_{3,3}$.


Embeddability of a graph in the **projective plane** is such a minor-closed property as well, and it is known that there are 35 forbidden minors that characterize projective planarity. All 35 minors are known, a recent reference from 2012 is, for example, <https://smartech.gatech.edu/bitstream/handle/1853/45914/Asadi-Shahmirzadi_Arash_201212_PhD.pdf>.  

A classical reference is *Graphs on Surfaces* from Mohar and Thomassen,
Johns Hopkins University Press 2001.


I am interested in the Colin de Verdière numbers for these 35 forbidden minors and have searched for them for a while now, but could not find anything.



> 
> **Question:** So I wondered whether the Colin de Verdière graph invariants for the whole set of these 35 forbidden minors are actually known? I would be grateful for any reference.
> 
> 
> 


UPDATE:  

Updating this question based on a great comment from Martin Winter. As he points out, the Colin de Verdière number $\mu$ is known and $\mu=4$ for a handful of these 35 forbidden minors, e.g. the disjoint unions of $K\_5$ and $K\_{3,3}$.


Interestingly, as outlined in his answer to a related question ([Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?](https://mathoverflow.net/q/368129/156936)), it follows that the Colin de Verdière invariant **cannot** provide a full characterization of graph embeddings e.g. in the projective plane.



Graph embeddings in the projective plane: for the 35 forbidden minors, do we know their Colin de Verdière numbers?
Here's a table containing the Colin de Verdière numbers:



```
Name        Graph6      μ   Reason
K33 + K33               4   (components linklessly embeddable)
K5  + K33               4   (components linklessly embeddable)
K5  + K5                4   (components linklessly embeddable)
K33 . K33               4   (apex)
K5  . K33               4   (apex)

K5  . K5                4   (apex)
B3          G~wWw{      4   (apex)
C2          H~wWooF     4   (apex)
C7          G~_kY{      4   (apex)
D1          Is[CKIC[w   4   (apex)

D4          H~AyQOF     4   (apex)
D9          I]op_oFIG   4   (apex)
D12         H^oopSN     4   (apex)  
D17         G~_iW{      4   (apex)
E6          Is[BkIC?w   4   (apex)
        
E11         I]op_oK?w   4   (apex)
E19         H~?guOF     4   (apex)
E20         H~_gqOF     4   (apex)
E27         I]op?_NAo   4   (apex)
F4          Is[?hICOw   4   (apex)

F6          Is[@iHC?w   4   (apex)
G1                      4   (apex)
K35                     4   (apex)
K45-4K2                 4   (apex)
K44-e                   5   (Petersen family and -2 argument)

K7-C4                   4   (apex)
D3          G~sghS      4   (apex)
E5          H]oxpoF     5   (Petersen family and -2 argument)
F1          H]ooXCL     4   (apex)
K1222                   4   (apex)

B7                      4   (apex)
C3                      4   (apex)
C4                      4   (apex)
D2                      4   (apex)
E2                      4   (apex)

```

Let me give justification. Graphs with $\mu \leq 3$ are planar, hence embeddable on the projective plane. So all the $35$ graphs have $\mu \geq 4$. Since apex graphs are linklessly embeddable, and linklessly embeddable graphs have $\mu \leq 4$, the apex graphs in this table have exactly $\mu = 4$. Also, a graph is linklessly embeddable iff its components are linklessly embeddable, so the first three graphs have $\mu = 4$.


The graphs in the [Petersen family](https://en.wikipedia.org/wiki/Petersen_family) are not linklessly embeddable, so they have $\mu \geq 5$. $K\_{4,4}-e$ is already in the Petersen family, and $\mathcal E\_5$ contains $K\_{3,3,1}$ as a subgraph. They both have $\mu \geq 5$.


To see they have $\mu \leq 5$, use Theorem 2.7 in [[1]](https://homepages.cwi.nl/%7Elex/files/cdvsurvey_new2.pdf): If $G=(V,E)$ is a graph, and $v$ a vertex of $G$, then $\mu(G) \leq \mu(G-v)+1$. Since we can remove $2$ vertices from $K\_{4,4}-e$ to make it planar (by making it $K\_{3,3}-e$), it follows that $\mu(K\_{4,4}-e) \leq \mu(K\_{3,3}-e)+2 = 5$. Hence $\mu(K\_{4,4}-e)=5$. The same line of reasoning applies to the graph $\mathcal E\_5$.


[1] Van Der Holst, Hein, László Lovász, and Alexander Schrijver. "The Colin de Verdiere graph parameter." Graph Theory and Computational Biology (Balatonlelle, 1996) (1999): 29-85.


