



Introduction
============

The <span>*crossing number*</span> $\crg(G)$ of a graph $G$ is the minimum number of (pairwise) edge crossings in a drawing of $G$ in the plane. To resolve ambiguity, we consider drawings of graphs such that no edge passes through another vertex and no three edges intersect in a common point which is not their end. A <span>*crossing*</span> is then an intersection point of two edges that is not a vertex, and we always assume a finite number of crossings.

If a graph has many (e.g., more than linear amount of) edges, then its crossing number must obviously be high. However, even graphs with few edges (e.g., cubic ones) may have quite high crossing number if there is "a lot of nonplanarity" in them. The latter is precisely captured through the critical obstructions:

-   A graph $G$ is <span>*$c$-crossing-critical*</span> if $\crg(G)\ge c$, but for every edge $e$ of $G$ we have $\crg(G-e)<c$ (i.e., the crossing number drops down in every proper subgraph).

Note that our graphs, and in particular the crossing-critical graphs, may not be simple, but one may always subdivide parallel edges without changing the crossing number.

There are two $1$-crossing-critical graphs up to subdivisions, $K_5$ and $K_{3,3}$, but for every $c\geq2$ there exists an infinite number of $c$-crossing-critical graphs. The latter has been first established by a nowadays classical construction of Kochol @kochol87, depicted in Figure \[fig:crcrbasics\]. The same picture also shows another notable crossing-critical construction from @cit:pathcrit. These two constructions outline the two basic principles used in all constructions of infinite $c$-crossing-critical families ever since; using a suitably chosen "planar belt" which is joined at the ends twisted (as the Möbius strip), and similarly, a "planar belt" which is joined straight (as on a cylinder) and then crossed by a suitably attached additional edge(s).

(a)

\[scale=0.53\] =\[draw, shape=circle, minimum size=2.5pt,inner sep=0pt, fill=black\] =\[color=black\] iin <span>0,...,3</span> <span> in <span>1,-1</span> <span> </span></span> (-1,0) – (21,0); (-1,1) – (0,1); (-1,2) – (21,2); iin <span>0,1</span> <span> (24\*i-2,2\*i) – (24\*i-2,1); (24\*i-2,1) – (24\*i-2,2-2\*i); </span>

\
(b)

\[scale=0.58\] (0,-0.5) rectangle (23.2,3.6); =\[draw, shape=circle, minimum size=2.5pt,inner sep=0pt, fill=black\] =\[color=black\] iin <span>1,...,20</span> <span> (i,0) – (i+2,2); (i,2) – (i+2,0); at (i+0.5,0.5) ; at (i+1,1) ; at (i+1.5,1.5) ; </span> (0,0) rectangle (1.95,2); (21.05,0) rectangle (23,2); (u) at (8,-1) ; (u1) at (5,0) ; (u2) at (12,0) ; (v) at (13,3) ; (v1) at (9,2) ; (v2) at (16,2) ; (u) .. controls (10,0) and (11,2) .. (v); (u) to\[bend right=12\] (u2); (u) to\[bend left=14\] (u1); (v) to\[bend left=12\] (v2); (v) to\[bend right=14\] (v1); iin <span>1,22</span> <span> (i,0) – (i,1); (i,1) – (i,2); </span>

A long-sought asymptotic characterization of $c$-crossing-critical families (for every fixed $c$) has been proved only recently by Dvořák et al. @dvorakHlinenyMohar18, confirming the experience with the two kinds of crossing-critical constructions described in the previous paragraph. These mentioned constructions, in particular, naturally have an upper bound on the maximum degree of the constructed graphs in terms of $c$. However, the characterization given in @dvorakHlinenyMohar18 leaves room for a rather obscure third possibility of a construction in which, informally saying, a part of the twisted planar belt boundary (as in Figure \[fig:crcrbasics\](a)) "collapses" into a single vertex of high degree. The existence of such a construction for high values of $c$ has been implicitly confirmed already by Dvořák and Mohar @cit:dvorakmohar, but no explicit examples were known until a more recent exhaustive work of Bokal et al. @bokal2019bounded:

\[Bokal, Dvoř<span>á</span>k, Hliněn<span>ý</span>, Lea<span>ñ</span>os, Mohar and Wiedera @bokal2019bounded, 2019\]  \[thm:main13\]\
a) For each $1\leq c\leq12$, there exists a constant $D_c$ such that every $c$-crossing-critical graph has vertex degrees at most $D_c$.\
b) For each $c\geq13$ and every integers $m,d$, there exists a $c$-crossing-critical graph which has more than $m$ vertices of degree at least $d$. (This statement is constructive.)

The critical construction of Theorem \[thm:main13\](b) is outlined for $c=13$ in Figure \[fig:main13\] (to be precise, the conference version of @bokal2019bounded contained a slightly different construction, the current one is from the full improved version of the paper on arXiv). Figure \[fig:main13\](a) defines the $17$-vertex $13$-crossing-critical (multi)graph $G_{13}$ which is the base graph of the full inductive construction. One can see in @bokal2019bounded that the proof of Theorem \[thm:main13\](b) follows straightforwardly (using induction) from the fact that $\crg(G_{13})\geq13$. However, for the latter fact only a machine-readable computer proof is provided in @bokal2019bounded; the proof is based on an ILP branch-and-cut-and-price routine @chimaniWiedera16 with about a thousand cases of up to hundreds of constraints each. Our goal is to provide a much simpler handwritten proof.

(a)

\[scale=1.04\] (-6.5,-1) rectangle (6,3); (x) at (-0.98,0) <span>$x_1$</span>; (xx) at (-0.02,0) <span>$x_2$</span>; (u1) at (-2,0) <span>$u_1$</span>; (u2) at (-3,0) <span>$u_2$</span>; (u3) at (-4,0) <span>$u_3$</span>; (u4) at (-5,0) <span>$u_4$</span>; \[label=above:

($u_5\!=\!w_2^1$)

\] (u5) at (-6,0.5) <span>$u_5$</span>; (v1) at (1,0) <span>$v_1$</span>; (v2) at (2,0) <span>$v_2$</span>; (v3) at (3,0) <span>$v_3$</span>; (v4) at (4,0) <span>$v_4$</span>; \[label=above:

($w_3^4\!=\!v_5$)

\] (v5) at (5,0.5) <span>$v_5$</span>; (h2) at (-3,1.35) <span>$w^{1}_1$</span>; (h3) at (-1.7,2) <span>$w^{1}_4$</span>; (k1) at (-0.5,3.2) <span>$w^2_2$</span>; (k2) at (0.7,2) <span>$w^{2}_1$</span>; (k3) at (2,1.35) <span>$w^{2}_4$</span>; (x) to\[in=0, out=160\] (u5); (xx) to\[out=20, in=180\] (v5); (u5) – node <span>$4$</span> (u4) – node <span>$3$</span> (u3) – node <span>$4$</span> (u2) – node <span>$5$</span> (u1) – node <span>$7$</span> (x) – node <span>$7$</span> (xx) – node <span>$7$</span> (v1) – node <span>$5$</span> (v2) – node <span>$4$</span> (v3) – node <span>$3$</span> (v4) – node <span>$4$</span> (v5); (u2) edge\[bend right=19\] (v3) (u3) edge\[bend right=19\] (v2) (u1) edge\[bend right=32\] node <span>2</span> (v4) (u4) edge\[bend right=32\] node <span>2</span> (v1) ; (u5) edge\[thick\] node <span>2</span> (h2) (h2) – (h3) (h3) edge\[thick\] node <span>2</span> (k1) (k1) edge\[bend right=10\] (u5) (k1) edge\[thick\] node <span>2</span> (k2) (k2) – (k3) (k3) edge\[thick\] node <span>2</span> (v5) (v5) edge\[bend right=10\] (k1) (h2) – (x) – (h3) (k2) – (xx) – (k3) ;

\[on background layer\] (x.center) – (h2.center) – (u5.center) – (-3.4,2.2) – (k1.center) – (h3.center) – cycle; (xx.center) – (k3.center) – (v5.center) – (2.4,2.2) – (k1.center) – (k2.center) – cycle;

(b)

\[xscale=0.9, yscale=0.75\] (-6.4,-1.3) rectangle (8,4.7); (x) at (-1,0) ; (x1) at (0,0) ; (xx) at (2,0) ; (u1) at (-2,0) ; (u2) at (-3,0) ; (u3) at (-4,0) ; (u4) at (-5,0) ; (u5) at (-6,0.35) ; (v1) at (3,0) ; (v2) at (4,0) ; (v3) at (5,0) ; (v4) at (6,0) ; (v5) at (7,0.35) ; (g1) at (-3,3.3) ; (h1) at (0.5,4) ; (h2) at (1.5,2.66) ; (h3) at (2.7,2.44) ; (k1) at (4,3.3) ; (k2) at (3.7,2) ; (k3) at (4.5,1.3) ; (x) to\[in=10, out=160\] (u5); (xx) to\[out=20, in=170\] (v5); (u5) – node <span>$4$</span> (u4) – node <span>$3$</span> (u3) – node <span>$4$</span> (u2) – node <span>$5$</span> (u1) – node <span>$7$</span> (x) – node <span>$7$</span> (x1) – node <span>$7$</span> (xx) – node <span>$7$</span> (v1) – node <span>$5$</span> (v2) – node <span>$4$</span> (v3) – node <span>$3$</span> (v4) – node <span>$4$</span> (v5); (u2) edge\[bend right=22\] (v3) (u3) edge\[bend right=22\] (v2) (u1) edge\[bend right=32\] node <span>2</span> (v4) (u4) edge\[bend right=32\] node <span>2</span> (v1) ; (h1) edge\[thick\] node <span>2</span> (h2) (h2) – (h3) (h3) edge\[thick\] node <span>2</span> (k1) (k1) edge\[bend right=10\] (h1) (k1) edge\[thick\] node <span>2</span> (k2) (k2) – (k3) (k3) edge\[thick\] node <span>2</span> (v5) (v5) edge\[bend right=10\] (k1) (h2) – (xx) – (h3) (k2) – (xx) – (k3) ;

\[on background layer\] (x.center) to\[bend right=28\] (u5.center) to\[bend left=10\] (g1.center) to\[bend right=12\] cycle; (x1.center) to\[bend right=16\] (g1.center) to\[bend left=10\] (h1.center) to\[bend right=16\] cycle; (xx.center) – (h2.center) – (h1.center) – (2.3,3.8) – (k1.center) – (h3.center) – cycle; (xx.center) – (k3.center) – (v5.center) – (5.6,2) – (k1.center) – (k2.center) – cycle;

(label) at (153:3.75) <span>$\cdots$</span>; (label) at (105:3) <span>$\cdots$</span>; (label) at (1,0.25) <span>$\cdots$</span>;

\[a computer-free alternative to Theorem \[thm:main13\](b)\] \[thm:main13alt\] $\crg(G_{13})\geq13$.

Analyzing optimal drawings of $G_{13}$
======================================

We divide the proof of Theorem \[thm:main13alt\] into two steps. We call <span>*red*</span> the edges of $G_{13}$ (Fig. \[fig:main13\](a)) which form the path with multiple edges on $(u_5,u_4,u_3,u_2,u_1,x_1,x_2,v_1,v_2,v_3,v_4,v_5)$, and we call <span>*blue*</span> the edges with one end $u_i$ and other end $v_j$ where $i,j\in\{1,2,3,4\}$.

(1) We will first show that there is an <span>*optimal drawing*</span> (i.e., one minimizing the number of crossings) of $G_{13}$ such that no red edge crosses a red or a blue edge. Note that blue–blue crossings are still allowed (and likely to occur).

(2) Secondly, while considering drawings as in the first point, we will refine our analysis by counting only selected crossings (roughly, those involving a blue edge), and prove at least $13$ of them, or at least $12$ with the remaining drawing still being non-planar.

Before proceeding further, we need some basic facts about the crossing number.

\[folklore\]\[pro:folklorecr\] a) If $D$ is an optimal drawing of a graph $G$, then no two edges cross more than once and edges sharing a common end do not cross at all in $D$.\
b) If $e$ and $f$ are parallel edges in $G$ (i.e., $e,f$ have the same end vertices), then there is an optimal drawing of $G$ in which $e$ and $f$ are drawn "closely together", meaning that they cross the same other edges in the same order.

In view of Proposition \[pro:folklorecr\](b), we adopt the following view of multiple edges: If the vertices $u$ and $v$ are joined by $p$ parallel edges, we view all $p$ of them as one edge $f$ of <span>*weight $p$*</span>. If (multiple) edges $f$ and $g$ of weights $p$ and $q$ cross each other, then their crossing naturally contributes the amount of $p\cdot q$ to the total number of crossings. This folklore observation greatly simplifies the analysis of our graph $G_{13}$ which contains many multiple edges.

We now, with help of the previous observations, finish the first step:

\[lem:redbluecr\] There exists an optimal drawing of the graph $G_{13}$ in which no red edge crosses a red or a blue edge, or $\crg(G_{13})\geq13$.

Note that the drawing in Fig. \[fig:main13\](a) is of the kind anticipated by Lemma \[lem:redbluecr\] (and there are also other drawings of $G_{13}$ with $13$ crossings of this kind, which can be very different from that of Fig. \[fig:main13\](a)), but we do not known yet whether they are optimal.

Let $D$ be an optimal drawing of $G_{13}$ with less than $13$ crossings. By Proposition \[pro:folklorecr\], if two red edges cross in $D$, then it can only be that an edge from $\{u_5u_4,u_4u_3,$ $u_3u_2\}$ crosses an edge from $\{v_5v_4,v_4v_3,v_3v_2\}$, which gives $3\cdot3=9$ or $3\cdot4=12$ crossings. Consider the edge-disjoint cycles $C_1=(u_5,u_4,u_3,u_2,u_1,x_1)$ and $C_2=(u_5,u_4,u_3,u_2,u_1,x_1,w_1^1)$, and symmetric $C_1'=(v_5,\dots,v_1,x_1)$, $C_2'=(v_5,\dots,v_1,x_1,w_1^1)$. Since $C_1,C_2$ transversely cross $C_1',C_2'$, they must cross a second time by the Jordan curve theorem, giving additional $2\cdot2=4$ crossings. Hence $D$ had at least $9+4=13$ crossings, and $\crg(G_{13})\geq13$.

It remains to get rid of possible red–blue crossings in $D$. Assume first that the red edge $x_1x_2$ (weight $7$) is crossed by a blue edge $e$. If $e$ is of weight $2$, then $D$ has $14$ crossings. Hence, up to symmetry, $e=u_3v_2$. We redraw $e$ tightly along the path $P=(u_3,u_4,v_1,v_2)$, saving $7$ crossings on $x_1x_2$, and newly crossing $u_4v_1$ (possibly) and $p$ edges which cross $P$ in $D$. If $p\geq3$, there are already $7+p\cdot2\geq13$ crossings in $D$. Otherwise, redrawing $e$ makes only $p+2\leq4$ new crossings, contradicting optimality of $D$.

In the rest, we usually remove unwanted red–blue crossings by redrawing the involved blue edge, while not increasing the total number of crossings. Since we always remove some red–blue crossing, this will eventually lead to a desired optimal drawing of $G_{13}$.

Assume in $D$ that a red edge $v_3v_4$ (or, symmetrically $u_4u_3$) is crossed by blue $e$, and this is the blue crossing on $v_3v_4$ closest to $v_3$. In this case, $e$ has one end $w\in\{v_1,v_2\}$. Instead of crossing $v_3v_4$ (saving $3$ crossings), we redraw part of $e$ tightly along the path $(v_3,v_2,v_1)$ to the end $w$, while possibly crossing blue $v_3u_2$, $v_2u_3$ (if $w=v_1$), and other $r$ edges which in $D$ cross red $v_3v_2$ or $v_2v_1$. If $r\geq3$, we already had $r\cdot4+3\geq15$ crossings in $D$. If $r\geq2$ and $e=v_1u_4$ (weight $2$), we had $r\cdot4+3\cdot2\geq14$ crossings in $D$. Otherwise, redrawn $e$ crosses at most $3$ new edges, and so we have no more crossings than in $D$.

Finally, if the red edge $v_4v_5$ is crossed by blue $e$ in $D$, then we "pull" the end $v_5$ along $v_4v_5$ towards $v_4$ across $e$. This redrawing replaces the crossing of $e$ with $v_4v_5$ of weight $4$ by $4$ crossings with the non-red edges of $v_5$, so again no more crossings than in $D$. If red $v_3v_2$ ($v_2v_1$, or $v_1x_2$) is crossed by blue $e$ in $D$, we similarly "pull" along the red edges $v_3$ towards $v_2$ ($v_2,v_3$ towards $v_1$, or $v_1,v_2,v_3$ towards $x_2$). This replaces the original crossing of $e$ with red by crossings of $e$ with $v_3v_4$ and $v_3u_2$ (plus $v_2u_3$ or plus $v_2u_3,v_1u_4$), but the total number of crossings stays the same as in $D$. Then we redraw the crossing of $e$ and $v_3v_4$ as above.

Refined counting of crossings in a drawing of $G_{13}$
======================================================

In the second step, we introduce two additional sorts of edges of $G_{13}$. The edges $u_5x_1$ and $v_5x_2$ are called <span>*green*</span>, and all remaining edges of $G_{13}$ (i.e., not blue or red or green) are declared <span>*gray*</span>. Let $G_0$ denote the subgraph of $G_{13}$ formed by all red and gray edges and the incident vertices. Let $R$ denote the (multi)path of all red edges.

\[lem:redgrayplanar\] Let $D$ be an optimal drawing of the graph $G_{13}$ as claimed by Lemma \[lem:redbluecr\]. If the subdrawing of $G_0$ within $D$ is planar, then $D$ has at least $13$ crossings.

a) 

\[xscale=0.55,yscale=0.75\] (x) at (-0.98,0) ; (xx) at (-0.02,0) ; (u1) at (-2,0) ; (u2) at (-3,0) ; (u3) at (-4,0) ; (u4) at (-5,0) ; (u5) at (-6,0) ; (v1) at (1,0) ; (v2) at (2,0) ; (v3) at (3,0) ; (v4) at (4,0) ; (v5) at (5,0) ; (h2) at (-3,1.35) ; (h3) at (-1.7,2) ; (k1) at (-0.5,3.2) ; (k2) at (0.7,2) ; (k3) at (2,1.35) ; (u5) – (u4) – (u3) – (u2) – (u1) – (x) – (xx) – (v1) – (v2) – (v3) – (v4) – (v5); (u5) edge\[thick\] node <span>2</span> (h2) (h2) – (h3) (h3) edge\[thick\] node <span>2</span> (k1) (k1) edge\[bend right=16\] (u5) (k1) edge\[thick\] node <span>2</span> (k2) (k2) – (k3) (k3) edge\[thick\] node <span>2</span> (v5) (v5) edge\[bend right=16\] (k1) (h2) – (x) – (h3) (k2) – (xx) – (k3) ;

\[on background layer\] (x.center) – (h2.center) – (u5.center) – (-3.4,2.2) – (k1.center) – (h3.center) – cycle; (xx.center) – (k3.center) – (v5.center) – (2.4,2.2) – (k1.center) – (k2.center) – cycle;

b)

\[xscale=0.5,yscale=0.6\] (-6.5,-1.75) rectangle (6,3.3); (x) at (-0.98,0) ; (xx) at (-0.02,0) ; (u1) at (-2,0) ; (u2) at (-3,0) ; (u3) at (-4,0) ; (u4) at (-5,0) ; (u5) at (-6,0) ; (v1) at (1,0) ; (v2) at (2,0) ; (v3) at (3,0) ; (v4) at (4,0) ; (v5) at (5,0) ; (h2) at (-3,1.35) ; (h3) at (-1.7,2) ; (k1) at (-0.5,3.2) ; (k2) at (0.7,-2) ; (k3) at (2,-1.35) ; (u5) – (u4) – (u3) – (u2) – (u1) – (x) – (xx) – (v1) – (v2) – (v3) – (v4) – (v5); (u5) edge\[thick\] node <span>2</span> (h2) (h2) – (h3) (h3) edge\[thick\] node <span>2</span> (k1) (k1) edge\[bend right=16\] (u5) (k1) edge\[thick,out=-5,in=90\] node <span>2</span> (6,0) (6,0) edge\[thick,out=-90,in=5\] (k2) (k2) – (k3) (k3) edge\[thick\] node <span>2</span> (v5) (v5) edge\[bend right=10\] (k1) (h2) – (x) – (h3) (k2) – (xx) – (k3) ;

\[on background layer\] (x.center) – (h2.center) – (u5.center) – (-3.4,2.2) – (k1.center) – (h3.center) – cycle; (xx.center) – (k3.center) – (v5.center) – (6,0) – (5.7,-1) – (4.5,-1.7) – (k2.center) – cycle; (v5.center) – (6,0) – (5.7,1.2) – (4.1,2.6) – (k1.center) – (2.4,2) – cycle;

\[Proof sketch\] There are only two non-equivalent planar drawings of $G_0$, as in Fig. \[fig:tworedgray\]. We picture them with the red path $R$ drawn as a horizontal line. We call a blue edge of $G_{13}$ <span>*bottom*</span> if it is attached to $R$ from below at both ends, and <span>*top*</span> if attached from above at both ends. A blue edge is <span>*switching*</span> if it is neither top nor bottom. Note that we have only crossings involving a green edge, or crossings of a blue edge with a blue or gray edge.

Consider the drawing of $G_0$ in Fig. \[fig:tworedgray\](a). By the Jordan curve theorem, we deduce:

(I) If a blue edge $e$ is bottom (top), and a blue edge $e'\not=e$ attaches to $R$ from below (from above) at its end which is between the ends of $e$ on $R$, then $e$ and $e'$ cross. In particular, two bottom (two top) blue edges always cross each other.

(II) A switching blue edge crosses at least $3$ gray edges, and a top one at least $4$.

(III) If there is weight $k$ of top (or switching) blue edges and $\ell$ of bottom blue edges, then each (or at least one) green edge must cross $\min(k,\ell)\leq3$ blue or red edges.

Say, if all blue edges are bottom, they pairwise give desired ${6\choose2}-2=13$ crossings by (I). If one of blue $u_4v_1,u_1v_4$ is top (or switching) and all other blue edges are bottom, we get at least $5+2\cdot4+4=17$ crossings (or $5+2\cdot3+2=13$ crossings) by the claims (I), (II) and (III) in this order. If one of $u_3v_2,u_2v_3$ is top (or switching) and all other blue are bottom, we similarly get $8+4+2=14$ crossings (or $10+3+1=14$ crossings) by (I),(II),(III), and so on. One may solve all other combinations of types of the blue edges using the same arguments, and we omit the routine technical details here.

Consider the other drawing of $G_0$ in Fig. \[fig:tworedgray\](b). Now a top or bottom blue edge must cross at least $2$ gray edges, and a switching blue edge at least $3$ gray edges. Hence we get desired $13$ crossings, unless all blue edges are top or bottom, giving the minimum of $6\cdot2=12$ blue-gray crossings. Though, then we get another blue crossing as in (I).

We now focus on selected crossings in a drawing of $G_{13}$: a <span>*refined crossing*</span> is one in which a blue edge crosses a gray or green edge, or two blue edges cross each other.

\[lem:redgraynonplanar\] Let $D$ be a drawing of the graph $G_{13}$ as claimed by Lemma \[lem:redbluecr\]. If $D$ has less than $13$ crossings and no red edge is crossed in $D$, then $D$ contains $12$ refined crossings.

\[Proof sketch\] We may again picture the red path $R$ as a straight horizontal line, and use the terms <span>*top/bottom/switching*</span> for blue edges as in the proof of Lemma \[lem:redgrayplanar\]. Then we consider the following six pairwise edge-disjoint gray and green paths: $P_1$ (of length $2$) and $P_2$ (of length $6$) join $u_5$ to $v_5$ via $w_2^2$,  $Q_1$ and $Q_1'$ are formed by the edges $u_5x_1$ and $v_5x_2$, and $Q_2,Q_2'$ (of length $2$) join $u_5$ to $x_1$ via $w_1^1$ and $v_5$ to $x_2$ via $w_4^2$. Using the Jordan curve theorem (cf. Fig. \[fig:main13\]), we deduce:

1.  The same claim for blue–blue crossing as (I) in the proof of Lemma \[lem:redgrayplanar\] applies here.

2.  If a blue edge $e$ is switching, then $e$ adds refined crossings on both $P_1$ and $P_2$.

3.  If the sum of weights of the blue edges attached to $u_1,u_2,u_3,u_4$ on $R$ from below is $k$ (and so $6-k$ from above), then each of $Q_1,Q_2$ carries at least $\min(k,6-k)$ unique crossings with blue edges in $D$. This symmetrically applies to $Q_1',Q_2'$.

Now it remains to examine all combinations of the blue edges being top/bottom/ switching, and in each use the above claims to argue that $D$ contains at least $12$ refined crossings. E.g., if $u_3v_2$ is top, $u_2v_3$ is switching and both $u_1v_4,u_4v_1$ are bottom, then we get by (I$'$) $2\cdot2=4$ crossings, by (II$'$) additional $2$ crossings and by (III$'$) additional $2\cdot(1+2)=6$ crossings. We omit the remaining routine technical details here.

We have now reached our goal of finding a simple computer-free proof of $\crg(G_{13})\geq13$:

\[<span>*Proof of Theorem \[thm:main13alt\].* </span>\] Let $D$ be an optimal drawing of $G_{13}$ satisfying the conclusion of Lemma \[lem:redbluecr\]. Thanks to Lemma \[lem:redgrayplanar\], we may assume that the subdrawing of $G_0$ within $D$ is not planar. If the red edges of $G_0$ are not crossed, we have a crossing of two gray edges of $G_0$ in $D$ and $12$ more refined crossings by Lemma \[lem:redgraynonplanar\], altogether $13$.

If some red edge is crossed in a point $x$ by a gray or green edge $g$ (since $g$ is not blue by Lemma \[lem:redbluecr\]), we redraw $g$ as follows: Up to symmetry, let $x$ be closer (or equal) to $v_5$ than to $u_5$ on $R$. We cut the drawing of $g$ at $x$ and route both parts of $g$ closely along their side of the drawing of $R$, until we rejoin them at the end $v_5$. This redrawing $D'$ saves $\ell\in\{3,4,5,7\}$ crossings of $g$ at $x$, and creates at most $\ell-1$ new refined crossings only between $g$ and the blue edges ending on $R$ between $x$ and $v_5$, as one can check in Fig. \[fig:main13\]. (We possibly repeat the same procedure for other crossings of red edges in $D$.)

We now apply Lemma \[lem:redgraynonplanar\] to $D'$, finding $\geq12$ refined crossings. Hence, $D$ contained at least $12-(\ell-1)$ refined crossings and $\ell$ other crossings at $x$, summing to $13$.

Conclusion
==========

With the computer-free proof of Theorem \[thm:main13alt\], we have completed a thorough study of high and possibly unbounded vertex degrees in $c$-crossing-critical graphs. Still, there is an unanswered secondary question about what exact high degrees can be achieved, say, for $c=13$. Looking at the construction in Fig. \[fig:main13\], we see that the two vertices $x_1$ and $x_2$ can attain any odd degree at least $17$, and possible additional vertices on the red path between $x_1$ and $x_2$ (in the expanded construction) can attain any combination of even degrees at least $16$, independently of each other. A slight modification of this construction of $13$-crossing-critical graphs allowing for any combination of arbitrarily many even <span>*and*</span> odd degrees is the subject of our continuing research.

Appendix: Full proofs of Lemmas \[lem:redgrayplanar\] and \[lem:redgraynonplanar\]  {#appendix-full-proofs-of-lemmaslemredgrayplanar-andlemredgraynonplanar .unnumbered}
===================================================================================

For the sake of completeness, we add full technical details for the proof sketches of Lemmas \[lem:redgrayplanar\] and \[lem:redgraynonplanar\] from the main paper body.

\[Proof of Lemma \[lem:redgrayplanar\]\] We first add further details for the claims (II) and (III). We refer to Fig. \[fig:main13\](a). In (II); for a top edge $f$ (which cannot cross $R$) we argue that $f$ must cross the four edge-disjoint gray paths $(u_5,w_1^1,x_1)$, $(u_5,w_1^1,w_4^1,x_1)$, $(v_5,w_4^2,x_2)$, and $(v_5,w_4^2,w_1^2,x_2)$. For switching $f$, which up to symmetry attaches to $u_i$ from above, we argue that $f$ must cross the three edge-disjoint gray paths $(u_5,w_1^1,x_1)$, $(u_5,w_1^1,w_4^1,x_1)$ and $(u_5,w_2^2,w_1^2,x_2)$.

In (III); considering (possibly parallel) $k$ top and $\ell$ bottom blue edges, the drawings of each cycle consisting of one top, one bottom, and between two and six interconnecting red edges separates $x_1$ from $u_5$ and $x_2$ from $v_5$, and so there must be an additional crossing on each of the green edges $u_5x_1$ and $x_2v_5$. There are $\min(k,\ell)\leq3$ such edge-disjoint cycles, and hence the claimed minimum number of crossings with each green edge. For switching and bottom blue edges, we get the same conclusion only for one of the two green edges.

We discuss the case of $G_0$ as in Fig. \[fig:tworedgray\](a) according to the number of bottom edges. If no blue edge is bottom, then we have at least $6\cdot3=18$ crossings by (II). If the combined weight of the bottom edges is at most $2$, then we have at least $4\cdot3=12$ crossings by (II), plus a crossing by (III). If the combined weight of the bottom edges equals $3$, then we have $2$ crossings by (I), at least $3\cdot3=9$ crossings by (II), and at least $2$ crossings by (III), summing to $\geq13$. If the combined weight of the bottom edges equals $4$, then we have at least $5$ crossings by (I), at least $2\cdot3=6$ crossings by (II), and at least $2$ crossings by (III), summing again to $\geq13$. The cases in which the weight of the bottom edges is $5$ or $6$ have already been solved in the proof sketch.

\[Proof of Lemma \[lem:redgraynonplanar\]\] Let $E_1$ and $E_2$ be the sets of top and bottom blue edges, in any order (our arguments are symmetric in top/bottom edges). Let $E_s$ be the set of switching blue edges. The claims (II$'$) and (III$'$) are argued very similarly to the proof of Lemma \[lem:redgrayplanar\]. We now review their exclusive contribution to the total number of crossings:

a)  (II$'$) $2\cdot|E_s|$ crossings by the switching blue edges to the paths $P_1, P_2$, and

b)  (III$'$) $\min_{p+q=|E_s|} \big(2\min(|E_1|+p,|E_2|+q)+2\min(|E_1|+q,|E_2|+p)\big)$ crossings by the blue edges to the paths $Q_1, Q_1^\prime, Q_2,Q_2^\prime$.

Unlike in the previous proof, we now have many dissimilar tight or nearly tight cases, and so we summarize all cases (one by one) in Table \[tbl2\]. In this summary we respect the symmetry between $E_1$ and $E_2$, and list the edges in $E_1,E_2,E_s$ only by their weights since only the weights really matter in (I$'$), (II$'$) and (III$'$).

     $E_1$      $E_2$      $E_s$          <span> </span>   <span> </span>   total
  ----------- --------- ----------- ---- ---------------- ---------------- -------
      {}         {}      {1,1,2,2}   0          12               0           12
      {1}        {}       {1,2,2}    0          10               2           12
      {2}        {}       {1,1,2}    0          8                4           12
      {1}        {1}       {2,2}     0          8                4           12
     {1,1}       {}        {2,2}     1          8                4           13
     {1,2}       {}        {1,2}     2          6                6           14
      {2}        {1}       {1,2}     0          6                6           12
      {2}        {2}       {1,1}     0          4                8           12
     {2,2}       {}        {1,1}     4          4                4           12
    {1,1,2}      {}         {2}      5          4                4           13
     {1,2}       {1}        {2}      2          4                8           14
      {2}       {1,1}       {2}      1          4                8           13
      {2}       {1,2}       {1}      2          2                10          14
     {2,2}       {1}        {1}      4          2                6           12
    {1,2,2}      {}         {1}      8          2                2           12
     {1,2}      {1,2}       {}       4          0                12          16
    {1,2,2}      {1}        {}       8          0                4           12
      {2}      {1,1,2}      {}       5          0                8           13
     {2,2}      {1,1}       {}       5          0                8           13
   {1,1,2,2}     {}         {}       13         0                0           13

  : The complete case analysis for the proof of Lemma \[lem:redgraynonplanar\]<span data-label="tbl2"></span>

{'source': 'arXiv_out/2105'}