# Strong Brandt-Thomassé Theorems

Tomasz Łuczak  Adam Mickiewicz University, Faculty of Mathematics and Computer
Science, Poznań, Poland<EMAIL_ADDRESS>,  Joanna Polcyn  Adam Mickiewicz
University, Faculty of Mathematics and Computer Science, Poznań, Poland
<EMAIL_ADDRESS>and  Christian Reiher  Fachbereich Mathematik, Universität
Hamburg, Hamburg, Germany<EMAIL_ADDRESS>
###### Abstract.

Solving a long standing conjecture of Erdős and Simonovits, Brandt and
Thomassé proved that the chromatic number of each triangle-free graph $G$ such
that $\delta(G)>|V(G)|/3$ is at most four. In fact, they showed the much
stronger result that every maximal triangle-free graph $G$ satisfying this
minimum degree condition is a blow-up of either an Andrásfai or a Vega graph.

Here we establish the same structural conclusion on $G$ under the weaker
assumption that for $m\in\\{2,3,4\\}$ every sequence of $3m$ vertices has a
subsequence of length $m+1$ with a common neighbour. In forthcoming work this
will be used to solve an old problem of Andrásfai in Ramsey-Turán theory.

###### Key words and phrases:

Extremal graph theory, triangle-free, Ramsey-Turán theory.

###### 2010 Mathematics Subject Classification:

Primary: 05C75, Secondary: 05C35, 05C07, 05C15.

The first author is partially supported by National Science Centre, Poland,
grant 2022/47/B/ST1/01517.

##  1\. Introduction

###  1.1. Minimum degree conditions

One of the earliest results of modern graph theory is Mantel’s theorem [M]
from 1907 on the maximum number of edges in a triangle-free graph. The
interest in the structure of dense triangle-free graphs has been revived in
the early seventies. Andrásfai, Erdős, and Sós [AES] observed that all
triangle-free graphs $G$ with $n$ vertices and minimum degree $\delta(G)>2n/5$
are bipartite. Moreover, Hajnal constructed a family of triangle-free graphs
$G$ with minimum degree $(1/3-o(1))|V(G)|$ and arbitrarily large chromatic
number. Inspired by this example Erdős and Simonovits [ES73] conjectured in
1973 that every triangle-free graph $G$ with $n$ vertices and minimum degree
$\delta(G)>n/3$ is three-colourable. In fact, at this time the only known
maximal triangle-free graphs $G$ on $n$ vertices with minimum degree
$\delta(G)>n/3$ were blow-ups of Andrásfai graphs, which were introduced by
Andrásfai [A] a few years earlier. For every positive integer $k$ there is an
Andrásfai graph $\Gamma_{k}$ with vertex set ${\mathds{Z}}/(3k-1){\mathds{Z}}$
and all edges $ij$ such that $i-j\in\\{k,k+1,\dots,2k-1\\}$. Hence, we have
$\Gamma_{1}=K_{2}$, $\Gamma_{2}=C_{5}$, and Figure 1.1 shows some further
Andrásfai graphs. By a blow-up of a given graph $G$ we mean another graph
obtained by replacing each vertex of $G$ by a non-empty independent set of
vertices and each edge of $G$ by the complete bipartite graph between the
vertex classes corresponding to its end vertices.

Figure 1.1. The Andrásfai graphs $\Gamma_{3}$, $\Gamma_{4}$, $\Gamma_{5}$, and
$\Gamma_{6}$.

Häggkvist [H] refuted the Erdős-Simonovits conjecture in the early eighties.
His counterexample is a blow-up of a certain triangle-free graph $\Upsilon$ on
eleven vertices with chromatic number four, often called the Mycielski graph
[Myc] by Polish authors (see Figure 1.2(a)) or the Grötzsch graph by German
authors (see Figure 1.2(b)). An appropriate choice of ‘weights’ indicated in
Figure 1.2(c) leads to blow-ups $\hat{\Upsilon}$ on $n$ vertices with
$\delta(\hat{\Upsilon})\geq 10n/29>n/3$.

Later work of Chen, Jin, and Koh [CJK] showed that containing $\Upsilon$ is
the only possible obstruction to satisfying the Erdős-Simonovits conjecture.
More precisely, all $\\{K_{3},\Upsilon\\}$-free graphs $G$ on $n$ vertices
with $\delta(G)>n/3$ are contained in blow-ups of Andrásfai graphs and,
therefore, three-colourable.

(a) Mycielski

(b) Grötzsch

(c) Häggkvist

${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$$x$$y$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}3i-2}$
(d) Vega

Figure 1.2. Some relevant graphs.

Brandt and Pisanski [BP], on the other hand, discovered that the Mycielski-
Grötzsch graph starts a new sequence of four-chromatic triangle-free graphs,
which they called Vega graphs; they have chromatic number four and admit
(regular) blow-ups violating the Erdős-Simonovits conjecture. Following some
further work on triangle-free graphs of large minimum degree (see, e.g., [L,
T]) Brandt and Thomassé then proved in an unpublished manuscript [BT] that
every maximal triangle-free graph $G$ on $n$ vertices with $\delta(G)>n/3$ is
a blow-up of either an Andrásfai graph or a Vega graph. It follows that all
such graphs are four-colourable, which establishes a relaxed version of the
Erdős-Simonovits conjecture.

Given their importance, we would briefly like to describe Vega graphs here.
For every integer $i\geq 2$ the graph $\Upsilon_{i}^{00}$, shown in Figure
1.2(d), consists of an inner Andrásfai graph $\Gamma_{i}$, an external hexagon
$\mathcal{C}_{6}={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$,
and two outer vertices $x$, $y$ joined to each other and to $\mathcal{C}_{6}$
as in the picture. Moreover, the vertices of $\mathcal{C}_{6}$ are connected
to the vertices of $\Gamma_{i}$ of the same colour (red, green, or blue).
There are further Vega graphs $\Upsilon_{i}^{10}$, $\Upsilon_{i}^{01}$, and
$\Upsilon_{i}^{11}$ obtained from $\Upsilon_{i}^{00}$ by deleting one or both
of $y$ and
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$.
For instance,
$\Upsilon_{2}^{11}=\Upsilon_{2}^{00}-\\{i,{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}3}\\}$
is isomorphic to the Mycielski-Grötzsch graph $\Upsilon$ (see Figure 4.3). A
more detailed definition of Vega graphs will be given at the beginning of
Section 4.

###  1.2. Existence of common neighbours

Our main result is similar to the Brandt-Thomassé theorem, but instead of a
minimum degree hypothesis we shall use an assumption on the existence of
common neighbours. The motivation for studying such problems is another
conjecture on dense triangle-free graphs due to Andrásfai. In his already
referenced article [A] he proposes to investigate the largest number
$\mathrm{ex}(n,s)$ of edges that a triangle-free graph on $n$ vertices can
have if its independence number is at most $s$. So for $s\geq n/2$ we have
$\mathrm{ex}(n,s)=\lfloor n^{2}/4\rfloor$ by Mantel’s theorem. After proving
that for $s\in(2n/5,n/2]$ certain blow-ups of $\Gamma_{2}$ are optimal,
Andrásfai conjectured that for every $s>n/3$ the maximum $\mathrm{ex}(n,s)$ is
achieved by an appropriate blow-up of some Andrásfai graph. His work is the
first contribution to a branch of extremal graph theory nowadays called
Ramsey-Turán theory. For some recent partial results on Andrásfai’s conjecture
we refer to [Vega, LPR2, LPR3]. An excellent survey by Sós and Simonovits [SS]
provides further background on Ramsey-Turán theory.

In a forthcoming article we plan to resolve Andrásfai’s conjecture in the
sense of establishing

$\mathrm{ex}(n,s)=\frac{1}{2}k(k-1)n^{2}-k(3k-4)ns+\frac{1}{2}(3k-4)(3k-1)s^{2}$
(1.1)

whenever $s\in(n/3,n/2]$ and $k=\lceil s/(3s-n)\rceil$. As explained in [Vega]
there is always a blow-up of $\Gamma_{k}$ achieving equality and for some
values of $k$ there are (perhaps unexpected) blow-ups of Vega graphs for which
equality holds as well. There will be one step in the proof of (1.1), where we
want to infer that some auxiliary graph $\mathscr{F}$ admits a homomorphism
into some ‘well-behaved’ graph, such as an Andrásfai or Vega graph. This graph
$\mathscr{F}$ is always triangle-free, but it can have vertices of small
degree. Thus we need to prove a version of the Brandt-Thomassé theorem under
an assumption which will turn out to hold in our intended application, and
this is what we shall do here. The alternative hypothesis is of the following
form.

######  Definition 1.1.

A graph $G$ has property $\mathcal{D}_{k}$ for some $k\in{\mathds{N}}$ if for
every $m\in[k]$ and every sequence $x_{1},\dots,x_{3m}\in V(G)$ of (not
necessarily distinct) vertices of $G$ there is a vertex $y\in V(G)$ such that

$|\\{i\in[3m]\colon x_{i}y\in E(G)\\}|\geq m+1\,.$

A simple counting argument discloses that every graph $G$ on $n$ vertices with
$\delta(G)>n/3$ has the property $\mathcal{D}_{k}$ for every $k\geq 1$. One
advantage of these properties, however, is that they are preserved under
taking blow-ups. That is, a graph $G$ satisfies $\mathcal{D}_{k}$ if and only
if all its blow-ups do. Another feature of $\mathcal{D}_{k}$ is that—in
contrast to the minimum degree condition—it is a sensible property of infinite
graphs. We offer some further remarks on this topic in the last section, but
throughout the main body of this article we shall tacitly assume that our
graphs are finite.

######  Theorem 1.2.

A maximal triangle-free graph satisfies $\mathcal{D}_{4}$ if and only if it is
a blow-up of either an Andrásfai or a Vega graph.

Therefore the class of blow-ups of Andrásfai and Vega graphs is definable by a
single first order property of graphs, which seems somewhat surprising to us.
Andrásfai and Vega graphs themselves are then definable as twin-free graphs in
this class, which is another first-order property. Next, the difference
between Andrásfai and Vega graphs is that the former are $\Upsilon$-free,
while the latter contain $\Upsilon$. We thus arrive at the astonishing
conclusion that both the class of Andrásfai graphs and the class of Vega
graphs are definable by a first-order sentence in the language of graph
theory.

The proof of Theorem 1.2 begins with a case distinction whether the given
graph $G$ is $\Upsilon$-free or not. If it is, we look at a maximal Andrásfai
subgraph $\Gamma_{k}$ of $G$ and show that $G$ is a blow-up of $\Gamma_{k}$.
Similarly, if $\Upsilon\subseteq G$ we take a maximal Vega subgraph of $G$ and
argue that $G$ is a blow-up thereof. It turns out that in the former case the
property $\mathcal{D}_{3}$ rather than $\mathcal{D}_{4}$ suffices. As it
reflects the historical progress made by Chen, Jin, Koh [CJK] and Brandt,
Thomassé [BT], we would like to state this fact separately.

######  Theorem 1.3.

Let $G$ be a maximal triangle-free graph.

  1. ( )

If $\Upsilon\nsubseteq G$ and $G$ satisfies $\mathcal{D}_{3}$, then $G$ is a
blow-up of some Andrásfai graph.

  2. ( )

If $\Upsilon\subseteq G$ and $G$ satisfies $\mathcal{D}_{4}$, then $G$ is a
blow-up of some Vega graph.

Finally it should be pointed out that many, but presumably not all, steps in
the earlier works [CJK, BT] use only $\mathcal{D}_{4}$ rather than the full
force of $\delta(G)>n/3$. So there is some overlap between our proof and the
arguments employed by Chen, Jin, and Koh [CJK], and by Brandt and Thomassé
[BT].

### Organisation

In the next section we introduce the central concepts of our approach and
provide a brief description of important intermediate steps. The proofs of the
parts ( ) ‣ 1.3 and ( ) ‣ 1.3 of Theorem 1.3 will then be completed in Section
3 and Section 4, respectively. We conclude by mentioning an even stronger
version of Theorem 1.3 and discussing some problems for further research in
Section 5.

##  2\. Preliminaries

We follow standard graph theoretic notation. Given a graph $G$ we denote its
sets of vertices and edges by $V(G)$ and $E(G)$, respectively. For brevity we
often write $xy\in E(G)$ instead of $\\{x,y\\}\in E(G)$. By $\mathrm{N}(v)$ we
mean the neighbourhood of $v\in V(G)$. The graph obtained from $G$ by removing
a vertex $v$ together with all incident edges is denoted by ${G-v}$. If $H$ is
a subgraph of $G$ and $v\in V(G)\smallsetminus V(H)$, then $H+v$ refers to the
graph

$\bigl{(}V(H)\cup\\{v\\},E(H)\cup\\{vx\in E(G)\colon x\in V(H)\\}\bigr{)}\,.$

Two vertices $v$, $w$ are called twins if they have the same neighbourhood,
i.e., $\mathrm{N}(v)=\mathrm{N}(w)$. Since a maximal triangle-free graph $G$
has property $\mathcal{D}_{k}$ if and only if all its blow-ups have this
property, it would suffice to prove our main result for twin-free graphs $G$.
But in order to detect twins in the graphs $G$ under consideration we shall
work with the following slightly more general concept.

######  Definition 2.1.

Let $H$ be a subgraph of $G$. If $q\in V(H)$ and $q^{\prime}\in V(G)$ satisfy

$\mathrm{N}(q)\cap V(H)=\mathrm{N}(q^{\prime})\cap V(H)\,,$

then $q^{\prime}$ is called an $H$-twin of $q$ (see Figure 2.1(a)).

Notice that every $q\in V(H)$ is an $H$-twin of itself. Moreover, if
$q^{\prime}\not\in V(H)$, then the graph $H-q+q^{\prime}$, which will be
denoted by $H(q^{\prime})$ in the sequel, is isomorphic to $H$. Now we are
ready to define a central concept of our approach.

######  Definition 2.2.

Let $F$ and $G$ be two graphs.

  1. ( )

For an edge $e\in E(F)$ we say that $G$ has the $(F,e)$-twin property if the
following holds:

> If $H$ is a subgraph of $G$ isomorphic to $F$, the edge $qz\in E(H)$
> corresponds to $e$, and $q^{\prime},z^{\prime}\in V(G)$ are $H$-twins of
> $q$, $z$, then $q^{\prime}z^{\prime}$ is an edge of $G$ (see Figure 2.1(b)).

  2. ( )

If $G$ has the $(F,e)$-twin property for every $e\in E(F)$, we say that $G$
has the $F$-twin property.

$G$$H$$q$$q^{\prime}$ (a) The vertex $q^{\prime}$ is an $H$-twin of $q$

$F$$e$$G$$H$$e$$z$$q$$q^{\prime}$$z^{\prime}$ (b) The graph $G$ has the
$(F,e)$-twin property

Figure 2.1. The concepts in Definitions 2.1 and 2.2.

Under some mild assumptions that will often be satisfied in what follows, the
next lemma asserts that if we want to prove a vertex $q^{\prime}$ to be an
$H$-twin of another vertex $q\in V(H)$, then we can temporarily replace some
vertex $z\in V(H-q)$ by any of its $H$-twins $z^{\prime}$.

######  Lemma 2.3.

Suppose that $F$ is a maximal triangle-free graph and $G$ is a triangle-free
graph possessing the $F$-twin property. Let $H$ be a copy of $F$ in $G$, let
$z^{\prime}\in V(G)\smallsetminus V(H)$ be an $H$-twin of $z\in V(H)$, and set
$H^{\prime}=H(z^{\prime})$.

If a vertex $q^{\prime}$ is an $H^{\prime}$-twin of $q\in
V(H)\smallsetminus\\{z\\}$, then it is an $H$-twin of $q$ as well.

###### Proof.

Knowing $\mathrm{N}(q^{\prime})\cap V(H^{\prime})=\mathrm{N}(q)\cap
V(H^{\prime})$ we want to show

$\mathrm{N}(q^{\prime})\cap V(H)=\mathrm{N}(q)\cap V(H)\,.$

So we only need to establish that $z$ is adjacent to either both or none of
$q$, $q^{\prime}$.

Assume first that $qz\notin E(G)$. Since $H$ is maximal triangle-free, there
is a vertex $y\in V(H)$ with $yq,yz\in E(G)$ (see Figure 2.2(a)). Because
$q^{\prime}$ is an $H^{\prime}$-twin of $q$ we obtain $yq^{\prime}\in E(G)$
(see Figure 2.2(b)) and the hypothesis $K_{3}\not\subseteq G$ yields indeed
$q^{\prime}z\not\in E(G)$.

Suppose next that $qz\in E(G)$, which entails $qz^{\prime}\in E(G)$, since
$z^{\prime}$ is an $H$-twin of $z$ (see Figure 2.2(c)). Due to
$H^{\prime}\cong H\cong F$ the $F$-twin property applies to the
$H^{\prime}$-twins $q^{\prime}$, $z$ of $q$, $z^{\prime}$. This shows that
$q^{\prime}z$ is an edge of $G$, thereby completing the proof (see Figure
2.2(d)). ∎

$G$$H^{\prime}$$z^{\prime}$$q$$z$$q^{\prime}$$y$ (a)

$G$$H^{\prime}$$z^{\prime}$$q$$z$$q^{\prime}$$y$ (b)

$G$$H^{\prime}$$z$$q^{\prime}$$q$$z^{\prime}$ (c)

$G$$H^{\prime}$$z$$q^{\prime}$$q$$z^{\prime}$ (d)

Figure 2.2. The proof of Lemma 2.3.

Let us now explain our strategy for proving that a given graph is a blow-up of
one of its subgraphs.

######  Lemma 2.4.

Let $G$ be a triangle-free graph and let $\Omega$ be a twin-free subgraph of
$G$ which is maximal triangle-free. If

  1. ( )

$G$ has the $\Omega$-twin property

  2. ( )

and every vertex of $G$ is an $\Omega$-twin of some vertex of $\Omega$,

then $G$ is a blow-up of $\Omega$.

In practice, assertions verifying assumption ( ) ‣ 2.4 will be called twin
lemmata and statements confirming ( ) ‣ 2.4 will be referred to as attachment
lemmata. Each of the two subsequent sections has its own twin lemma (cf. Lemma
3.3 and Lemma 4.28) and its own attachment lemma (cf. Lemma 3.4 and Lemma
4.29).

###### Proof of Lemma 2.4.

Set $A_{q}=\\{q^{\prime}\in V(G)\colon q^{\prime}\text{ is an $\Omega$-twin of
$q$}\\}$ for every $q\in V(\Omega)$. These sets are mutually disjoint, because
we assumed $\Omega$ to be twin-free. So due to ( ) ‣ 2.4 we have a partition

$V(G)=\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits_{q\in
V(\Omega)}A_{q}$

and ( ) ‣ 2.4 informs us that whenever $qz\in E(\Omega)$ all
$A_{q}$-$A_{z}$-edges are in $E(G)$. Since $\Omega$ is maximal triangle-free,
$G$ can have no further edges. ∎

##  3\. Andrásfai graphs

This entire section is devoted to the proof of part ( ) ‣ 1.3 of Theorem 1.3.
Our first step simplifies the assumption $\Upsilon\not\subseteq G$. Since the
Mycielski-Grötzsch graph $\Upsilon$ is maximal triangle-free, all its
occurrences in triangle-free graphs must be induced. Together with the fact
that $\Upsilon$ contains an induced hexagon this shows that triangle-free
graphs containing $\Upsilon$ contain an induced hexagon as well. It turns out
that this implication can be reversed for maximal triangle-free graphs with
property $\mathcal{D}_{3}$.

######  Lemma 3.1.

Let $G$ be a maximal triangle-free graph satisfying $\mathcal{D}_{3}$. If $G$
contains an induced hexagon, then it contains the Mycielski-Grötzsch graph as
well.

###### Proof.

Let $a_{1}-b_{3}-a_{2}-b_{1}-a_{3}-b_{2}-a_{1}$ be an induced hexagon. Its
vertex set has only two independent subsets of size three, namely
$\\{a_{1},a_{2},a_{3}\\}$ and $\\{b_{1},b_{2},b_{3}\\}$. So by
$\mathcal{D}_{2}$ we may assume that there exists a common neighbour $x$ of
$b_{1},b_{2}$, and $b_{3}$. Because $G$ is a maximal triangle-free graph and
$a_{1}b_{1},a_{2}b_{2},a_{3}b_{3}\not\in E(G)$, there are common neighbours
$c_{i}$ of $a_{i}$, $b_{i}$ for $i=1,2,3$ (see Figure 3.1(a)). Since $G$ is
triangle-free, the vertices $x$, $c_{1}$, $c_{2}$, $c_{3}$ are distinct.

$b_{1}$$a_{1}$$b_{3}$$a_{3}$$b_{2}$$a_{2}$$c_{1}$$c_{2}$$c_{3}$$x$ (a)

$b_{1}$$a_{1}$$b_{3}$$a_{3}$$b_{2}$$a_{2}$$c_{1}$$c_{2}$$c_{3}$$x$ (b)

$b_{1}$$a_{1}$$b_{3}$$a_{3}$$b_{2}$$a_{2}$$c_{1}$$c_{2}$$c_{3}$$x$$q$ (c)

$b_{2}$$x$$a_{1}$$c_{2}$$q$$a_{3}$$b_{3}$$c_{1}$$a_{2}$$c_{3}$$b_{1}$ (d)

Figure 3.1. The proof of Lemma 3.1.

By $\mathcal{D}_{3}$ there is a four-element subset $T$ of
$\\{a_{1},a_{2},a_{3},b_{1},b_{2},b_{3},c_{1},c_{2},c_{3}\\}$ possessing a
common neighbour $t$. As $T$ contains at most one vertex from each of the
edges $b_{1}c_{1}$, $b_{2}c_{2}$, $b_{3}c_{3}$, we may assume $a_{1}\in T$.
Similarly at least one of $b_{1}$, $b_{2}$, $b_{3}$ is in $T$. Together with
the independence of $T$ this yields $b_{1}\in T$, whence
$T=\\{a_{1},b_{1},c_{2},c_{3}\\}$. Thus we can replace $c_{1}$ by $t$ and this
argument allows us to assume $c_{1}c_{2},c_{1}c_{3}\in E(G)$ (see Figure
3.1(b)).

Next we apply $\mathcal{D}_{2}$ to the hexagon
$a_{2}-c_{2}-b_{2}-a_{3}-c_{3}-b_{3}-a_{2}$. Due to the symmetry between the
indices $2$ and $3$ we can suppose, without loss of generality, that there
exists a common neighbour $q$ of $a_{2}$, $b_{2}$, $c_{3}$ (see Figure
3.1(c)). Altogether we have now found a copy of the Mycielski-Grötzsch graph
$\Upsilon$ in $G$ (see Figure 3.1(d)). ∎

In the remainder of this section we do not need to appeal to $\mathcal{D}_{3}$
directly anymore. In other words, we shall obtain an explicit description of
the class $\mathfrak{A}$ of maximal triangle-free graphs on at least two
vertices not containing an induced hexagon. As it will turn out,
$\mathfrak{A}$ is simply the class of blow-ups of Andrásfai graphs. Let us
recall at this moment that for every positive integer $k$ the Andrásfai graph
$\Gamma_{k}$ has vertex set ${\mathds{Z}}/(3k-1){\mathds{Z}}$ and all edges
$ij$ such that $i-j\in\\{k,k+1,\dots,2k-1\\}$. As promised in Section 2 we
shall establish a twin lemma and an attachment lemma.

An edge $ij$ of the Andrásfai graph $\Gamma_{k}$ is called short if $i-j=\pm
k$ and long otherwise. So all edges of $\Gamma_{1}$ and $\Gamma_{2}$ are short
and, up to symmetry, $04$ is the only long edge of $\Gamma_{3}$. For long
edges the twin property requires no further assumptions.

######  Lemma 3.2.

If $e$ denotes a long edge of an Andrásfai graph $\Gamma_{k}$, then every
$G\in\mathfrak{A}$ has the $(\Gamma_{k},e)$-twin property.

###### Proof.

We start with the special case $k=3$, i.e., we show that every
$G\in\mathfrak{A}$ has the $(\Gamma_{3},04)$-twin property. Assume
contrariwise that $\Gamma_{3}\subseteq G$ and that $0^{\prime},4^{\prime}\in
V(G)$ are non-adjacent $\Gamma_{3}$-twins of $0,4\in V(\Gamma_{3})$. Let $r$
be a common neighbour of $0^{\prime}$, $4^{\prime}$ (see Figure 3.2(a)).

$r$$3$$2$$1$$0$$7$$6$$5$$4$$4^{\prime}$$0^{\prime}$ (a)

$r$$3$$2$$1$$0$$7$$6$$5$$4$$4^{\prime}$$0^{\prime}$ (b)

$r$$3$$2$$1$$0$$7$$6$$5$$4$$4^{\prime}$$0^{\prime}$ (c)

Figure 3.2. The $(\Gamma_{3},e)$-twin property.

As the hexagon $0^{\prime}-r-4^{\prime}-7-2-5-0^{\prime}$ cannot be induced,
we have $2r\in E(G)$ (see Figure 3.2(b)). Similarly, the hexagon
$0^{\prime}-r-4^{\prime}-1-6-3-0^{\prime}$ discloses $6r\in E(G)$ (see Figure
3.2(c)). But now $26r$ is a triangle, which is absurd.

$0$$j$$k$$k-1$$j-k$$j+k$$2k$$2k-1$ (a) A copy of $\Gamma_{3}$ in $\Gamma_{k}$.

$r$$0^{\prime}$$k^{\prime}$$2k$$2k-1$$k$$k-1$$1$$0$$\dots$ (b) $1r\in E(G)$.

$r$$2k-1$$k$$k^{\prime}$$k-1$$1$$0^{\prime}$$0$$2k$$\dots$ (c) A copy of
$\Gamma_{k+1}$ in $G$.

Figure 3.3. The $\Gamma_{k}$-twin property for long and short edges.

Next we generalise this to all long edges. By symmetry we may assume that the
given long edge of $\Gamma_{k}$ is of the form $e=0j$, where $k<j<2k-1$.
Figure 3.3(a) shows a copy of $\Gamma_{3}$ in $\Gamma_{k}$ one of whose long
edges corresponds to $0j$. Thus the assertion follows from the special case
treated earlier. ∎

######  Lemma 3.3 (Twin lemma).

Every $\Gamma_{k+1}$-free graph $G\in\mathfrak{A}$ has the $\Gamma_{k}$-twin
property.

###### Proof.

It remains to consider short edges. In fact, for reasons of symmetry, it
suffices to show that $G$ has the $(\Gamma_{k},0k)$-twin property. Assume for
the sake of contradiction that $\Gamma_{k}\subseteq G$ and that $0^{\prime}$,
$k^{\prime}$ are non-adjacent $\Gamma_{k}$-twins of $0$, $k$, respectively.
Let $r$ be a common neighbour of $0^{\prime}$, $k^{\prime}$. Whenever $0<j<k$
the hexagon

$0^{\prime}-r-k^{\prime}-(j+2k-1)-j-(j+k)-0^{\prime}$

shows $rj\in E(G)$ (for $j=1$ this is illustrated in Figure 3.3(b)). So
$\\{0^{\prime},1,\dots,k-1,k^{\prime}\\}\subseteq\mathrm{N}(r)$ and
$V(\Gamma_{k})\cup\\{0^{\prime},k^{\prime},r\\}$ induces a copy of
$\Gamma_{k+1}$ in $G$, which is absurd (see Figure 3.3(c)). ∎

######  Lemma 3.4 (Attachment lemma).

If $\Gamma_{k}\subseteq G\in\mathfrak{A}$ and $G$ is $\Gamma_{k+1}$-free, then
every $q\in V(G)$ is a $\Gamma_{k}$-twin of some vertex of $\Gamma_{k}$.

###### Proof.

We begin with the following very special case.

######  Claim 3.5.

If $j\in V(\Gamma_{k})$, and $j+k,j-k\in\mathrm{N}(q)$, then $q$ is a
$\Gamma_{k}$-twin of $j$.

###### Proof.

By symmetry we can assume $j=k$, so that $0,2k\in\mathrm{N}(q)$. For every
vertex $m\in[2k+1,3k-2]$ the hexagon

$q-0-(m-k)-m-(m+k)-2k-q$

shows $qm\in E(G)$ (see Figure 3.4(a)). So $\mathrm{N}(k)\cap
V(\Gamma_{k})=\\{2k,\dots,3k-2,0\\}\subseteq\mathrm{N}(q)\cap V(\Gamma_{k})$
and, since $G$ is triangle-free, this holds with equality. ∎

$k$$m-k$$2k$$m$$m+k$$2k-1$$1$$0=3k-1$$q$ (a)

$k$$k+1$$2k$$k-1$$2k-1$$1$$0=3k-1$$3k-2$$q$$z$ (b)

Figure 3.4. The proof of the attachment lemma.

Let us proceed with a less special case.

######  Claim 3.6.

If $q$ has a neighbour in $V(\Gamma_{k})$, then it is a $\Gamma_{k}$-twin of
some vertex of $\Gamma_{k}$.

###### Proof.

By symmetry we can suppose that $kq\in E(G)$ and $(k-1)q\notin E(G)$. Let $z$
be a common neighbour of $k-1$ and $q$ (see Figure 3.4(b)). The hexagon

$z-q-k-0-(2k-1)-(k-1)-z$

shows that either $q(2k-1)$ or $z0$ is an edge. In the first case Claim 3.5
entails that $q$ is a $\Gamma_{k}$-twin of $0$. In the second case Claim 3.5
implies that $z$ is a $\Gamma_{k}$-twin of $2k-1$ and we can form
$\Gamma_{k}^{\prime}=\Gamma_{k}(z)$. Another application of Claim 3.5 reveals
that $q$ is a $\Gamma_{k}^{\prime}$-twin of $0$. Since $G$ has the
$\Gamma_{k}$-twin property, Lemma 2.3 tells us that $q$ is also a
$\Gamma_{k}$-twin of $0$. ∎

Proceeding with the general case we consider an arbitrary vertex $q\in V(G)$.
Assuming $0q\notin E(G)$ we take a common neighbour $z$ of $q$, $0$. We
already know that $z$ is a $\Gamma_{k}$-twin of some $j\in V(\Gamma_{k})$. Now
$q$ has a neighbour belonging to $\Gamma_{k}^{\prime}=\Gamma_{k}(z)$ and,
therefore $q$ is a $\Gamma_{k}^{\prime}$-twin of some $i\in
V(\Gamma_{k})\smallsetminus\\{j\\}$. By Lemma 2.3 $q$ is also a
$\Gamma_{k}$-twin of $i$. ∎

The main result of this section reads as follows.

######  Proposition 3.7.

A maximal triangle-free graph on at least two vertices contains no induced
hexagon if and only if it is a blow-up of some Andrásfai graph.

###### Proof.

We will only require and prove the forward implication in the sequel, leaving
the (almost obvious) reverse direction to the reader. Since the given graph
$G$ is maximal triangle-free and has at least two vertices, it needs to
contain a copy of $\Gamma_{1}$. Let $k\in{\mathds{N}}$ be maximal such that
$G$ has a subgraph isomorphic to $\Gamma_{k}$. By Lemma 3.3 and Lemma 3.4 the
assumptions of Lemma 2.4 are satisfied for some $\Omega\cong\Gamma_{k}$. Thus
$G$ is a blow-up of $\Gamma_{k}$. ∎

It should be clear that Lemma 3.1 combined with Proposition 3.7 yields Theorem
1.3( ) ‣ 1.3.

##  4\. Vega graphs

The goal of this section is to establish Theorem 1.3( ) ‣ 1.3. We start by
defining Vega graphs. For every $i\geq 2$ there is a Vega graph
$\Upsilon_{i}^{00}$ shown in Figure 4.1. In the middle we see an Andrásfai
graph $\Gamma_{i}$ together with a three-colouring
$V(\Gamma_{i})={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\Gamma_{\mathrm{green}}}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}$
of its vertex set, where
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}=\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0},\dots,{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}\\}$
is a set of red vertices, the set
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\Gamma_{\mathrm{green}}}=\\{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i},\dots,{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}\\}$
is green, and
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}=\\{{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i},\dots,{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}3i-2}\\}$
is blue. The vertices of the external hexagon
$\mathcal{C}_{6}={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$
are connected to the vertices of the same colour of the inner Andrásfai graph,
so that

${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}=\mathrm{N}({\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a})\cap\mathrm{N}({\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u})\,,\qquad{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\Gamma_{\mathrm{green}}}=\mathrm{N}({\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b})\cap\mathrm{N}({\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v})\,,\quad\text{
and
}\quad{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}=\mathrm{N}({\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c})\cap\mathrm{N}({\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w})\,.$

Finally, there is an edge $xy$ joined to the hexagon so that

$\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}\\}\subseteq\mathrm{N}(x)\quad\text{
and
}\quad\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}\\}\subseteq\mathrm{N}(y)\,.$

This completes the description of $\Upsilon_{i}^{00}$.

${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$$x$$y$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}3i-2}$
Figure 4.1. The Vega graph $\Upsilon_{i}^{00}$.

For each $i\geq 2$ there are three further Vega graphs
$\Upsilon_{i}^{10}=\Upsilon_{i}^{00}-y$,
$\Upsilon_{i}^{01}=\Upsilon_{i}^{00}-{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(2i-1)}$,
and
$\Upsilon_{i}^{11}=\Upsilon_{i}^{00}-\\{y,{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}\\}$.
Thus for $\mu,\nu\in\\{0,1\\}$ the vertex $y$ belongs to
$\Upsilon_{i}^{\mu\nu}$ if and only if $\mu=0$, while $\nu=0$ indicates the
presence of
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$.

###  4.1. Automorphisms

We will write $\mathrm{Aut}(\Omega)$ for the automorphism group of a given
graph $\Omega$, i.e., for the group of adjacency preserving bijections
$V(\Omega)\longrightarrow V(\Omega)$. The main reason why knowing
automorphisms of Vega graphs will be helpful for us is that they often allow
us to reduce the number of cases we need to consider. Moreover, they sometimes
suggest non-obvious embeddings of smaller Vega graphs into larger ones, that
are in turn useful when considering a maximal Vega subgraph of a given graph
$G$ we wish to analyse. In all cases, the lists of automorphisms we provide
could be shown to be exhaustive, but there is no need for verifying this.

We start with three automorphisms of order two that exist for all $i\geq 2$
and appropriate values of $\mu$, $\nu$. First, for both indices
$\nu\in\\{0,1\\}$ the composition $\sigma$ of the four transpositions

$x\longleftrightarrow
y\,,\qquad{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}\longleftrightarrow{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}\,,\qquad{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}\longleftrightarrow{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}\,,\qquad{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}\longleftrightarrow{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$

is an automorphism of $\Upsilon_{i}^{0\nu}$.

Second, $\Upsilon_{i}^{\mu 0}$ has an automorphism $\tau_{0}$ exchanging the
colours red and green. More precisely, $\tau_{0}$ is the composition of the
transpositions

${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}\longleftrightarrow{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}\,,\qquad{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}\longleftrightarrow{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$

with the reflection $j\longmapsto 2i-1-j$ of the inner Andrásfai graph.

Similarly, $\Upsilon_{i}^{\mu 1}$ has an automorphism $\tau_{1}$ exchanging
blue and green, namely the composition of

${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}\longleftrightarrow{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}\,,\qquad{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}\longleftrightarrow{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$

with the reflection $j\longmapsto i-1-j$ of
$\Gamma_{i}-({\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1})$.

It could be shown that for $i\geq 3$ these automorphisms generate the entire
automorphism group, i.e., that

$\mathrm{Aut}(\Upsilon^{\mu\nu}_{i})=\begin{cases}\\{1,\sigma,\tau_{0},\sigma\tau_{0}\\}&\text{if
}(\mu,\nu)=(0,0)\cr\\{1,\sigma,\tau_{1},\sigma\tau_{1}\\}&\text{if
}(\mu,\nu)=(0,1)\cr\\{1,\tau_{0}\\}&\text{if
}(\mu,\nu)=(1,0)\cr\\{1,\tau_{1}\\}&\text{if }(\mu,\nu)=(1,1),\end{cases}$

but we do not need this knowledge in the sequel.

What will be important, however, is that for $i=2$ and $(\mu,\nu)\neq(0,1)$
there are further ‘sporadic’ automorphisms. We begin their discussion with an
alternative way of drawing $\Upsilon_{2}^{00}$: Start with $\Gamma_{3}$, add
simultaneously four twins as indicated in Figure 4.2(a), and join them to a
new vertex.

${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$$x$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}3}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$$y$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$
(a)

${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$$x$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}3}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$$y$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$
(b)

${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$$x$$y$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}3}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}$
(c)

Figure 4.2. Three pictures of $\Upsilon_{2}^{00}$.

The dihedral group ${\mathds{D}}_{4}$ acts in the usual way by rotations and
reflections on the “imaginary square”
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}$.
This yields a faithful action of ${\mathds{D}}_{4}$ on $\Upsilon_{2}^{00}$
with fixed point $4$ and, in fact, it could be proved that

$\mathrm{Aut}(\Upsilon_{2}^{00})\cong{\mathds{D}}_{4}\,.$

We shall occasionally use the reflection $\varrho$ about the line
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$.
So explicitly $\varrho$ is the composition of the five transpositions

${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}\longleftrightarrow{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}\,,\qquad{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}\longleftrightarrow{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}\,,\qquad{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}\longleftrightarrow{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}\,,\qquad
x\longleftrightarrow{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}\,,\qquad{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}3}\longleftrightarrow
y$

(see Figure 4.19). As $\varrho$ exchanges
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}3}$
and $y$, it establishes an exceptional isomorphism between $\Upsilon_{2}^{01}$
and $\Upsilon_{2}^{10}$. More generally we shall always regard $\varrho$ as an
isomorphism from $\Upsilon_{2}^{\mu\nu}$ to $\Upsilon_{2}^{\nu\mu}$. The graph
$\Upsilon_{2}^{01}$ has only the four standard automorphisms mentioned
earlier.

Finally, $\Upsilon_{2}^{11}$ is isomorphic to the Mycielski-Grötzsch graph
(see Figure 4.3) and its automorphism group can be shown to be the symmetry
group ${\mathds{D}}_{5}$ of the “imaginary pentagon”
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}01}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}x{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$.

${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$$x$01243${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$$x$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}$
Figure 4.3. The isomorphism $\Upsilon^{11}_{2}\cong\Upsilon$.

Let us conclude this subsection by showing that we cannot obtain
$\Upsilon_{i}^{11}$ from $\Upsilon_{i}^{00}$ by deleting an edge.

######  Lemma 4.1.

If $i\geq 2$ and $q,z\in V(\Upsilon_{i}^{00})$ satisfy
$\Upsilon_{i}^{00}-\\{q,z\\}\cong\Upsilon_{i}^{11}$, then $qz\not\in
E(\Upsilon_{i}^{00})$.

###### Proof.

Assume contrariwise that for some edge $qz$ of $\Upsilon_{i}^{00}$ the graphs
$\Upsilon_{i}^{00}-\\{q,z\\}$ and $\Upsilon_{i}^{11}$ are isomorphic. We label
the vertices of $\Upsilon_{i}^{00}$ as in Figure 4.1. Recall that in
$\Upsilon_{i}^{11}$ any two non-adjacent vertices have a common neighbour.
Since
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$
is the only common neighbour of
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$
and
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$,
this proves that if
$q={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$,
then
$z\in\\{{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c},{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}\\}$.
But
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$
is also the only common neighbour of $y$ and
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}$
and, therefore,
$q={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$
would imply
$z\in\\{y,{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}\\}$
as well. Altogether the case
$q={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$
is impossible. By $\sigma$\- and $\tau_{0}$-symmetry this argument actually
shows

$q,z\not\in\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b},{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}\\}\,.$
(4.1)

We indicate degrees of vertices in $\Upsilon_{i}^{00}$ by $\mathrm{d}(\cdot)$.
Because of

$|E(\Upsilon_{i}^{00})|-|E(\Upsilon_{i}^{11})|=\mathrm{d}(y)+\mathrm{d}({\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1})=4+(i+2)=i+6$

and $qz\in E(\Upsilon_{i}^{00})$ we have

$\mathrm{d}(q)+\mathrm{d}(z)=i+7\,.$ (4.2)

As $\Upsilon^{00}_{i}$ has the degree table

$t\in$ | $\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b},{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}\\}$ | $\Gamma_{i}\cup\\{{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}\\}$ | $\\{x,y\\}$
---|---|---|---
$\mathrm{d}(t)=$ | $i+3$ | $i+2$ | $4$

,

it follows from (4.1) and (4.2) that $i=3$ and
$q,z\in\Gamma_{i}\cup\\{{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}\\}$.
It is not difficult to see, however, that if two adjacent vertices belonging
to this set are deleted from $\Upsilon_{i}^{00}$, then an even number of the
vertices
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b},{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$
keeps the degree $i+3$. The graph $\Upsilon^{11}_{i}$, on the other hand, has
exactly one such vertex (namely, the vertex which would be called
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$
in the standard labelling of $\Upsilon^{11}_{i}$). This contradiction
concludes the proof. ∎

###  4.2. Properties of maximal triangle-free graphs satisfying
$\mathcal{D}_{4}$

Let $\mathfrak{D}_{4}$ be the class of maximal triangle-free graphs satisfying
$\mathcal{D}_{4}$. In this subsection we present two lemmata on subgraphs of
such graphs. The first of them concerns the cube, that is the graph remaining
from $K_{4,4}$ after the deletion of a perfect matching. Brandt [B] proved
that maximal triangle-free graphs $G$ with $\delta(G)>|V(G)|/3$ contain no
induced cubes. His argument goes through under the weaker assumption
$G\in\mathfrak{D}_{4}$ and for the sake of completeness we would like to
provide full details.

######  Lemma 4.2 (Cube lemma).

No graph in $\mathfrak{D}_{4}$ contains an induced cube.

###### Proof.

Assume contrariwise that some $G\in\mathfrak{D}_{4}$ has eight vertices

$a_{1},a_{2},a_{3},a_{4},b_{1},b_{2},b_{3},b_{4}$

such that $a_{i}b_{j}\in E(G)$ whenever $i,j\in[4]$ are distinct, whilst
$a_{i}b_{i}\not\in E(G)$ for all $i\in[4]$.

$a_{2}$$a_{3}$$a_{4}$$a_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{1}$
(a)

$a_{2}$$a_{3}$$a_{4}$$a_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{1}$$t$
(b)

$a_{2}$$a_{3}$$a_{4}$$a_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{1}$$s$
(c)

$a_{2}$$a_{3}$$a_{4}$$a_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{1}$
(d)

Figure 4.4. The proof of the cube lemma.

Because $G$ has diameter two, there exist vertices
$c_{i}\in\mathrm{N}(a_{i})\cap\mathrm{N}(b_{i})$ for all $i\in[4]$ (see Figure
4.4(a)). By $\mathcal{D}_{4}$ there is a five-element set
$T\subseteq\\{a_{1},a_{2},a_{3},a_{4},b_{1},b_{2},b_{3},b_{4},c_{1},c_{2},c_{3},c_{4}\\}$
possessing a common neighbour $t$. Since $T$ contains at most one vertex from
each of the edges $b_{i}c_{i}$, we may assume $a_{4}\in T$. Similarly we
obtain $b_{4}\in T$ and thus $T=\\{a_{4},b_{4},c_{1},c_{2},c_{3}\\}$. So
$c_{4}$ can be replaced by $t$ (see Figure 4.4(b)) and, without loss of
generality, we may assume

$c_{1}c_{4},c_{2}c_{4},c_{3}c_{4}\in E(G)\,.$ (4.3)

Next we apply $\mathcal{D}_{3}$ to the nine vertices $a_{1}$, $a_{2}$,
$a_{3}$, $b_{1}$, $b_{2}$, $b_{3}$, $c_{1}$, $c_{2}$, $c_{3}$, thereby finding
a vertex $s$ which is, without loss of generality, adjacent to $a_{2}$,
$b_{2}$, $c_{1}$, $c_{3}$ (see Figure 4.4(c)). Replacing $c_{2}$ by $s$ we
change (4.3) to the more ‘symmetric’ configuration

$c_{1}c_{2},c_{2}c_{3},c_{3}c_{4},c_{4}c_{1}\in E(G)\,.$

But now the largest independent set among the twelve vertices $a_{i}$,
$b_{i}$, $c_{i}$ with $i\in[4]$ has size four, contrary to $\mathcal{D}_{4}$.
∎

In the sequel, whenever we apply the above lemma, we write

$(Q)$ |  | $a_{1}$ | $a_{2}$ | $a_{3}$ | $a_{4}$
---|---|---|---
$b_{1}$ | $b_{2}$ | $b_{3}$ | $b_{4}$

to denote the cube $Q$ with vertices $a_{i}$, $b_{i}$ and
$E(Q)=\\{a_{i}b_{j}\colon i\neq j\text{ and }i,j\in[4]\\}$. Notice that if $Q$
appears as a non-induced subgraph of some triangle-free graph $G$, then one of
the edges $a_{i}b_{i}$ needs to be present in $G$.

We shall now take a closer look at the graph $N$ displayed in Figure 4.5,
which we have already encountered in the proofs of Lemma 3.1 and Lemma 4.2. It
will be convenient to read the indices $0$, $1$, $2$ in $N$ modulo $3$. As we
have seen in earlier proofs, if $N$ is a subgraph of some graph $G$ satisfying
$\mathcal{D}_{3}$, then one of the three sets
$\\{a_{i},b_{i},c_{i+1},c_{i+2}\\}$ needs to have a common neighbour. It turns
out that for $G\in\mathfrak{D}_{4}$ much more is true.

$b_{0}$$c_{0}$$a_{0}$$b_{1}$$c_{1}$$a_{1}$$b_{2}$$c_{2}$$a_{2}$$N$$V(N)=\\{a_{i},b_{i},c_{i}\colon
i\in{\mathds{Z}}/3{\mathds{Z}}\\}$$E(N)=\\{a_{i}c_{i},b_{i}c_{i},a_{i}b_{j}\colon
i,j\in{\mathds{Z}}/3{\mathds{Z}},i\neq j\\}$ Figure 4.5. The graph $N$.

######  Lemma 4.3.

If $N$ is a subgraph of some $G\in\mathfrak{D}_{4}$, then for every
$i\in{\mathds{Z}}/3{\mathds{Z}}$ either $c_{i-1}c_{i+1}$ is an edge of $G$ or
there is a common neighbour of $a_{i}$, $b_{i}$, $c_{i-1}$, $c_{i+1}$.

###### Proof.

The only independent sets of size four in $N$ are

$\\{a_{0},b_{0},c_{1},c_{2}\\}\,,\qquad\\{a_{1},b_{1},c_{0},c_{2}\\}\,,\quad\text{
and }\quad\\{a_{2},b_{2},c_{0},c_{1}\\}\,.$

For every $i\in{\mathds{Z}}/3{\mathds{Z}}$ let $X_{i}$ be the set of common
neighbours of $a_{i}$, $b_{i}$, $c_{i-1}$, $c_{i+1}$. As $G$ satisfies
$\mathcal{D}_{3}$, the sets $X_{0}$, $X_{1}$, and $X_{2}$ cannot be empty
simultaneously and thus we can assume ${X_{0}\neq\varnothing}$. For reasons of
symmetry we only need to prove that if $c_{0}c_{2}\not\in E(G)$, then
$X_{1}\neq\varnothing$. To this end we consider a common neighbour $y$ of
$c_{0}$, $c_{2}$ (see Figure 4.6(a)).

$b_{0}$$c_{0}$$a_{0}$$b_{1}$$c_{1}$$a_{1}$$b_{2}$$c_{2}$$a_{2}$$y$ (a)

$b_{2}$$b_{0}$$c_{2}$$a_{0}$$a_{1}$$a_{2}$$y$$b_{1}$$c_{1}$$c_{0}$ (b)

$P$$x_{0}$$b_{2}$$z$$b_{0}$$c_{2}$$a_{0}$$a_{1}$$a_{2}$$y$$b_{1}$$c_{1}$$c_{0}$$e_{2}$$e_{1}$
(c)

$x_{0}$$b_{2}$$z$$b_{0}$$c_{2}$$a_{0}$$a_{1}$$a_{2}$$y$$b_{1}$$c_{1}$$c_{0}$$q$
(d)

Figure 4.6. The proof of Lemma 4.3.

Working with the hexagon $b_{0}a_{1}b_{2}a_{0}b_{1}a_{2}$ and the path
$c_{0}yc_{2}$ (see Figure 4.6(b)) we see that the graph $N+y-c_{1}$ has only
three independent sets of size four, namely

$\\{a_{1},b_{1},c_{0},c_{2}\\}\,,\qquad\\{a_{0},a_{1},a_{2},y\\}\,,\qquad\\{b_{0},b_{1},b_{2},y\\}\,.$

If the first of them has a neighbour we are done, so due to $\mathcal{D}_{3}$
and $a$-$b$-symmetry we can assume that there is a common neighbour $z$ of
$\\{a_{0},a_{1},a_{2},y\\}$. Together with an arbitrary vertex $x_{0}\in
X_{0}$ we can now build the configuration shown in Figure 4.6(c).

Let us now look at the set $A$ consisting of the nine vertices belonging to
the pentagon
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}P=b_{2}a_{1}b_{0}a_{2}c_{2}}$
and the two edges
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}e_{1}=yc_{0}}$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}e_{2}=c_{1}b_{1}}$
(see Figure 4.6(c)). By $\mathcal{D}_{3}$ there is an independent set
$U\subseteq A$ of size four possessing a common neighbour $q$. Clearly, $U$
contains two vertices from $P$ and one vertex from each of the edges
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}e_{1}}$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}e_{2}}$.

If $\\{b_{0},a_{2}\\}\cap U=\varnothing$, then only the possibility
$U=\\{c_{2},a_{1},c_{0},b_{1}\\}$ remains, and we reach $q\in X_{1}$, as
required. Now assume for the sake of contradiction that either $b_{0}$ or
$a_{2}$ is in $U$. Both cases can be treated analogously and we only display
the argument for $a_{2}\in U$. Now we have $\\{a_{2},c_{1},b_{2}\\}\subseteq
U$ and the largest independent set among the twelve vertices

$y,c_{0},q,c_{1},b_{2},z,b_{0},c_{2},a_{0},a_{1},a_{2},x_{0}$

has size four (see Figure 4.6(d)), contrary to $\mathcal{D}_{4}$. ∎

When using Lemma 4.3 in the sequel, we will sometimes draw the configuration
at hand as in Figure 4.7. The dashed orange non-edge forces the existence of a
green vertex together with four green edges.

Figure 4.7. Applications of Lemma 4.3.

###  4.3. Grötzsch subgraphs

In this subsection we label the vertices of the Mycielski-Grötzsch graph
$\Upsilon$ as shown in Figure 4.8(a). So the eleven vertices are called
$a_{i}$, $b_{i}$, $c$ with indices $i\in{\mathds{Z}}/5{\mathds{Z}}$, and the
twenty edges of $\Upsilon$ are all pairs of the form $a_{i}c$, $a_{i}b_{i\pm
2}$, or $b_{i}b_{i+2}$.

The results that follow deal with graphs $G$ such that $\Upsilon\subseteq
G\in\mathfrak{D}_{4}$. Here are some questions motivating them.

  1. $\bullet$

Which subsets of $V(\Upsilon)$ have common neighbours?

  2. $\bullet$

How far can we go in the direction of proving the $\Upsilon$-twin property?

At first sight some of the ensuing statements may seem very weak. This is
because we do not ‘know’ at the present level of generality how the given copy
of $\Upsilon$ ‘sits’ in the Vega graph of which $G$ is a blow-up, so that
there is still a large number of possibilities. For the very same reason,
however, the results obtained here turn out to be very flexible later, when we
study the scenario $\Upsilon_{i}^{\mu\nu}\subseteq G\in\mathfrak{D}_{4}$. The
fact that $\Upsilon_{i}^{\mu\nu}$ can contain ‘many’ copies of $\Upsilon$ then
means that results on $\Upsilon$ tend to be applicable in several distinct
ways.

######  Lemma 4.4 (Beautiful lemma).

If $i\in{\mathds{Z}}/5{\mathds{Z}}$, $\Upsilon\subseteq G\in\mathfrak{D}_{4}$,
and $q\in V(G)$ is adjacent to $a_{i-1}$, $a_{i+1}$, then $a_{i}q\in E(G)$.

###### Proof.

Due to symmetry we can assume $i=1$, so that $a_{0}q,a_{2}q\in E(G)$ (see
Figure 4.8(b)). Suppose $a_{1}q\not\in E(G)$ and let $z$ be a common neighbour
of $a_{1}$, $q$. The graph $\Upsilon-a_{3}+q+z$ can be drawn as in Figure
4.8(c). Its only independent set of size $5$ is
$\\{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}a_{0}},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}a_{4}},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b_{0}},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b_{4}},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}z}\\}$.
If $b_{2}^{\prime}$ denotes a common neighbour of this set guaranteed by
$\mathcal{D}_{4}$, then the graph $\Upsilon-b_{2}-a_{4}+b^{\prime}_{2}+q+z$
drawn in Figure 4.8(d) has no independent set of size five, which contradicts
$G\in\mathfrak{D}_{4}$. ∎

$c$$a_{2}$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$ (a)

$a_{0}$$b_{0}$$b_{4}$$c$$b_{3}$$b_{2}$$a_{2}$$a_{1}$$a_{3}$$b_{1}$$a_{4}$$q$
(b)

$a_{0}$$b_{0}$$b_{4}$$c$$b_{3}$$b_{2}$$a_{2}$$a_{1}$$a_{3}$$b_{1}$$a_{4}$$q$$z$
(c)

$a_{0}$$b_{0}$$b_{4}$$c$$b_{3}$$b_{2}^{\prime}$$a_{2}$$a_{1}$$a_{3}$$b_{1}$$a_{4}$$q$$z$
(d)

Figure 4.8. The proof of the beautiful lemma.

The Mycielski-Grötzsch graph has three kinds of edges. For those containing
the central vertex $c$ the twin property demands no additional assumptions.

######  Lemma 4.5.

For every $i\in{\mathds{Z}}/5{\mathds{Z}}$ all graphs $G\in\mathfrak{D}_{4}$
have the $(\Upsilon,ca_{i})$-twin property.

###### Proof.

Due to symmetry we can assume $i=1$. Suppose $\Upsilon\subseteq G$ and that
$a_{1}^{\prime},c^{\prime}\in V(G)$ are $\Upsilon$-twins of $a_{1}$, $c$.
Since $a_{0},a_{2}\in\mathrm{N}(c^{\prime})$, the beautiful lemma applied to
$\Upsilon(a_{1}^{\prime})$ and $c^{\prime}$ instead of $\Upsilon$ and $q$
yields $a_{1}^{\prime}c^{\prime}\in E(G)$. ∎

For the other edges of $\Upsilon$ the twin property cannot be proved
unconditionally. But the situation can be analysed satisfactorily as follows.

######  Lemma 4.6.

Let $i\in{\mathds{Z}}/5{\mathds{Z}}$, $\varepsilon\in\\{1,-1\\}$, and
$\Upsilon\subseteq G\in\mathfrak{D}_{4}$. If $a_{i}^{\prime}$,
$b^{\prime}_{i+2\varepsilon}$ are non-adjacent $\Upsilon$-twins of $a_{i}$,
$b_{i+2\varepsilon}$, then there exists a common neighbour of
$\\{a_{i}^{\prime},a_{i+2\varepsilon},b_{i+\varepsilon},b^{\prime}_{i+2\varepsilon}\\}$.

###### Proof.

By symmetry we can assume $i=0$ and $\varepsilon=1$. Let $r$ be a common
neighbour of $a_{0}^{\prime}$, $b_{2}^{\prime}$ (see Figure 4.9(a)). Due to
$a_{2}b_{1}\not\in E(G)$ our claim follows from Lemma 4.3 (see Figure 4.9(b)).
∎

$c$$a_{2}$$a_{3}$$a_{4}$$a^{\prime}_{0}$$a_{1}$$b_{0}$$b_{1}$$b^{\prime}_{2}$$b_{3}$$b_{4}$$r$
(a)

$b_{0}$$a_{2}$$c$$a_{4}$$b_{1}$$b_{3}$$a^{\prime}_{0}$$r$$b^{\prime}_{2}$ (b)

$c$$a_{2}$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b^{\prime}_{0}$$b_{1}$$b^{\prime}_{2}$$b_{3}$$b_{4}$$r$
(c)

$b_{4}$$b_{1}$$b_{3}$$a_{0}$$c$$a_{2}$$b^{\prime}_{0}$$r$$b^{\prime}_{2}$ (d)

Figure 4.9. The proofs of Lemma 4.6 and Lemma 4.7.

######  Lemma 4.7.

If $i\in{\mathds{Z}}/5{\mathds{Z}}$, $\Upsilon\subseteq G\in\mathfrak{D}_{4}$,
and $b^{\prime}_{i}$, $b^{\prime}_{i+2}$ are non-adjacent $\Upsilon$-twins of
$b_{i}$, $b_{i+2}$, then there is a common neighbour of
$\\{b_{i}^{\prime},b_{i+1},b^{\prime}_{i+2},c\\}$.

###### Proof.

It suffices to consider the case $i=0$. If $r$ denotes a common neighbour of
$b_{0}^{\prime}$, $b_{2}^{\prime}$ (see Figure 4.9(c)), then due to
$b_{1}c\not\in E(G)$ Lemma 4.3 leads to the desired vertex (see Figure
4.9(d)). ∎

The three foregoing lemmata will assist us later when proving the twin lemma
for Vega graphs (cf. Lemma 4.28). In an attempt to facilitate later references
we visualise the beautiful lemma and the two previous lemmata in Figure 4.10.
The idea is that in Figure 4.10(a) the existence of the two blue edges leads
to the green one. Moreover, in the Figures 4.10(b) and 4.10(c) the dashed
orange non-edge forces the existence of the green vertex together with four
green edges.

(a) Beautiful Lemma

(b) Lemma 4.6

(c) Lemma 4.7

Figure 4.10.

######  Lemma 4.8.

Let $\Upsilon\subseteq G\in\mathfrak{D}_{4}$. If $u\in V(G)$ is adjacent to
$a_{1}$, $a_{4}$ and $v\in V(G)$ is adjacent to $u$, $b_{0}$, then either
$b_{1}v\in E(G)$, or $b_{4}v\in E(G)$, or $v$ is adjacent to $\Upsilon$-twins
of $b_{1}$ and $b_{4}$.

$c$$a_{2}$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$u$$v$
(a)

$b_{1}^{\prime}$$b_{4}^{\prime}$$b_{3}$$b_{1}$$a_{4}$$b_{2}$$b_{4}$$a_{1}$$u$$v$$b_{0}$
(b)

$a_{3}$$b_{3}$$a_{1}$$a_{0}$$b_{0}$$b_{1}^{\prime}$$b_{1}$$u$$b_{2}$$v$$a_{4}$$b_{4}^{\prime}$
(c)

$a_{2}$$b_{2}$$a_{4}$$a_{0}$$b_{0}$$b_{4}^{\prime}$$b_{4}$$u$$b_{3}$$v$$a_{1}$$b_{1}^{\prime}$
(d)

Figure 4.11. The proof of Lemma 4.8.

###### Proof.

The beautiful lemma implies $a_{0}u\in E(G)$ (see Figure 4.11(a)). Suppose
that neither $b_{1}v$ nor $b_{4}v$ is an edge of $G$. Due to Lemma 4.3 there
are common neighbours $b_{1}^{\prime}$ and $b^{\prime}_{4}$ of
$\\{a_{4},b_{3},b_{4},v\\}$ and $\\{a_{1},b_{1},b_{2},v\\}$, respectively (see
Figure 4.11(b)).

It remains to show $a_{3}b_{1}^{\prime},a_{2}b_{4}^{\prime}\in E(G)$, for then
$b_{1}^{\prime}$, $b_{4}^{\prime}$ are the desired $\Upsilon$-twins in
$\mathrm{N}(v)$. Both statements follow from the beautiful lemma applied to
appropriate copies of $\Upsilon$, as indicated in the Figures 4.11(c) and
4.11(d). ∎

We proceed with a series of results that are drawn schematically in Figure
4.12. Again the blue vertices and edges and the orange dashed non-edges force
the existence of green vertices and edges. The colour light-green indicates
twins.

(a) Corollary 4.9

(b) Lemma 4.10

(c) Lemma 4.11

(d) Lemma 4.12

Figure 4.12.

######  Corollary 4.9.

Let $\Upsilon\subseteq G\in\mathfrak{D}_{4}$. If $q\in V(G)$ is adjacent to
$c$, $b_{0}$, then either $q$ is an $\Upsilon$-twin of $a_{2}$, or it is an
$\Upsilon$-twin of $a_{3}$, or it is adjacent to $\Upsilon$-twins of $b_{1}$
and $b_{4}$.

###### Proof.

Apply Lemma 4.8 to $u=c$ and $v=q$. ∎

The maximal independent sets of $\Upsilon$ are the neighbourhoods of vertices
and the five sets of the form $\\{a_{i-1},a_{i},a_{i+1},b_{i}\\}$. It can
happen that some of these sets have common neighbours in an ambient graph $G$
belonging to $\mathfrak{D}_{4}$. Given $i\in{\mathds{Z}}/5{\mathds{Z}}$ and
$\Upsilon\subseteq G$ we shall write $\mathrm{Ext}(\Upsilon,a_{i})$ for the
set of common neighbours of $\\{a_{i-1},a_{i+1},b_{i}\\}$. More generally, if
$\Omega\subseteq G$ is isomorphic to $\Upsilon$ and $a\in V(\Omega)$ has
degree three in $\Omega$, then $\mathrm{Ext}(\Omega,a)$ is defined
analogously. The beautiful lemma implies
$\mathrm{Ext}(\Omega,a)\subseteq\mathrm{N}(a)$. If
$\mathrm{Ext}(\Omega,a)=\varnothing$, we say that $a$ is reliable (with
respect to $\Omega$).

######  Lemma 4.10.

If $\Upsilon\subseteq G\in\mathfrak{D}_{4}$ and $q\in V(G)$ is adjacent to
$a_{1}$, $a_{4}$, then either $q$ is an $\Upsilon$-twin of $c$ or
$q\in\mathrm{Ext}(\Upsilon,a_{0})$.

###### Proof.

The beautiful lemma tells us $qa_{0}\in E(G)$. If
$q\not\in\mathrm{Ext}(\Upsilon,a_{0})$, then $qb_{0}\notin E(G)$ and we can
pick a common neighbour $z$ of $q$, $b_{0}$ (see Figure 4.13(a)). Plugging
$u=q$, $v=z$ into Lemma 4.8 we learn that either $zb_{1}\in E(G)$, or
$zb_{4}\in E(G)$, or $z$ is adjacent to $\Upsilon$-twins of both $b_{1}$,
$b_{4}$. By symmetry we may assume that $\mathrm{N}(z)$ contains some
$\Upsilon$-twin $b_{4}^{\prime}$ of $b_{4}$. As we only need to show
$a_{2},a_{3}\in\mathrm{N}(q)$, it is permissible to replace $\Upsilon$ by
$\Upsilon(b_{4}^{\prime})$ and, hence, we can even assume $b_{4}z\in E(G)$
(see Figure 4.13(b)).

$c$$a_{2}$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$q$$z$
(a)

$c$$a_{2}$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$q$$z$
(b)

$c$$a_{2}$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$q$$z$
(c)

$c^{\prime}$$z$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$q$
(d)

Figure 4.13. The proof of Lemma 4.10.

Due to $\mathcal{D}_{4}$ the graph $\Upsilon-a_{2}+q+z$ depicted in Figure
4.13(c) has an independent set $T$ of size five possessing a common neighbour
$c^{\prime}$. Since $T$ contains at most two vertices of the pentagon
$B={\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}b_{0}b_{2}b_{4}b_{1}b_{3}}$
and at most one vertex from each of the edges $qz$, $a_{3}c$, at least one of
$a_{0}$, $a_{1}$, $a_{4}$ needs to be in $T$. Thus $c$ and $q$ are not in $T$
or, in other words, $T$ is a subset of the ten-cycle
$b_{0}a_{3}b_{1}a_{4}b_{2}a_{0}b_{3}a_{1}b_{4}z$, whence
$T=\\{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}z},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}a_{0}},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}a_{1}},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}a_{3}},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}a_{4}}\\}$.

The beautiful lemma applied to $a_{4},z\in\mathrm{N}(q)$ and the graph
$\Upsilon-c-a_{2}+c^{\prime}+z$ drawn in Figure 4.13(d) shows
$a_{3}\in\mathrm{N}(q)$. A final application of the beautiful lemma to
$a_{1},a_{3}\in\mathrm{N}(q)$ and $\Upsilon$ gives $a_{2}\in\mathrm{N}(q)$,
wherefore $q$ is indeed an $\Upsilon$-twin of $c$. ∎

######  Lemma 4.11.

If $\Upsilon\subseteq G\in\mathfrak{D}_{4}$ and $q\in V(G)$ is adjacent to
$a_{0}$, $b_{1}$, but not to $a_{1}$, then it is adjacent to $b_{0}$ and to
some vertex in $\mathrm{Ext}(\Upsilon,a_{2})$.

$c$$a_{2}$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$q$$z$
(a)

$b_{4}$$b_{2}$$a_{0}$$c$$a_{3}$$b_{1}$$q$$z$$a_{1}$$t$ (b)

$b_{2}$$a_{4}$$b_{4}$$t$$b_{0}$$a_{0}$$b_{1}$$a_{1}$$a_{3}$$b_{3}$$c$$q$ (c)

Figure 4.14. The proof of Lemma 4.11.

###### Proof.

Let $z$ be a common neighbour of $q$, $a_{1}$ (see Figure 4.14(a)). In view of
$b_{2}a_{3}\notin E(G)$, Lemma 4.3 tells us that there is a common neighbour
$t$ of $q$, $a_{1}$, $b_{2}$, and $a_{3}$ (see Figure 4.14(b)). Clearly, $t$
is in $\mathrm{Ext}(\Upsilon,a_{2})$. Due to $a_{0},t\in\mathrm{N}(q)$ the
beautiful lemma applied to $\Upsilon-a_{2}+t$ yields $b_{0}\in\mathrm{N}(q)$
(see Figure 4.14(c)). ∎

######  Lemma 4.12.

If $\Upsilon\subseteq G\in\mathfrak{D}_{4}$ and $a_{0},b_{1}\in\mathrm{N}(q)$,
then either $q\in\mathrm{Ext}(\Upsilon,a_{1})$, or $b_{0}q\in E(G)$, or $q$ is
adjacent to $\Upsilon$-twins of $a_{2}$, $b_{0}$.

$c$$a_{2}$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$q$
(a)

$b_{4}$$a_{2}$$c$$a_{3}$$b_{0}$$b_{2}$$a_{0}$$q$$b_{1}$$b_{0}^{\prime}$ (b)

$b_{4}$$a_{2}$$c$$a_{3}$$b_{0}$$b_{2}$$a_{0}$$q$$b_{1}$$a_{2}^{\prime}$ (c)

$b_{4}$$a_{2}$$c$$a_{3}$$b_{0}$$b_{2}$$a_{0}$$q$$b_{1}$$b_{0}^{\prime}$$b_{3}$
(d)

Figure 4.15. The proof of Lemma 4.12.

###### Proof.

If $a_{2}q\in E(G)$, then $q\in\mathrm{Ext}(\Upsilon,a_{1})$ and we are done.
So we may suppose $a_{2},b_{0}\notin\mathrm{N}(q)$ and need to prove that
$\mathrm{N}(q)$ contains $\Upsilon$-twins of those two vertices. Due to Lemma
4.3 there are vertices $b^{\prime}_{0}$ and $a^{\prime}_{2}$ adjacent to
$\\{a_{2},a_{3},b_{2},q\\}$ and $\\{b_{0},b_{4},c,q\\}$, respectively (see
Figures 4.15(b) and 4.15(c)). Obviously $a_{2}^{\prime}$ is an $\Upsilon$-twin
of $a_{2}$. Moreover, the cube

$(Q)$ |  | $q$ | $b_{3}$ | $b_{2}$ | $a_{3}$
---|---|---|---
$b_{0}$ | $b_{0}^{\prime}$ | $b_{1}$ | $a_{0}$

drawn in Figure 4.15(d) yields $b_{0}^{\prime}b_{3}\in E(G)$ and thus
$b_{0}^{\prime}$ is an $\Upsilon$-twin of $b_{0}$. ∎

When applying one of the three previous lemmata it is often useful to know
that certain vertices in the copy of $\Upsilon$ under consideration are
reliable, as this could eliminate one of several possible outcomes. So far,
however, we have no way of inferring reliability. The last two lemmata of this
subsection change this situation.

######  Lemma 4.13.

If $\Upsilon\subseteq G\in\mathfrak{D}_{4}$, then at least one of $a_{1}$,
$a_{2}$, $a_{3}$ is reliable.

$c$$a_{2}$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$t_{1}$$t_{2}$$t_{3}$
(a)

$a_{4}$$b_{1}$$t_{1}$$a_{0}$$b_{3}$$t_{3}$$a_{2}$$t_{2}$$b_{2}$$q$ (b)

$a_{4}$$a_{0}$$a_{1}$$b_{1}$$b_{2}$$c$$b_{3}$$b_{4}$$q$$a_{2}$$t_{2}$$t_{3}$
(c)

Figure 4.16. The proof of Lemma 4.13.

###### Proof.

Assume contrariwise that there exist vertices
$t_{i}\in\mathrm{Ext}(\Upsilon,a_{i})$ for $i\in\\{1,2,3\\}$. Let us recall
that this means $a_{i-1},a_{i+1},b_{i}\in\mathrm{N}(t_{i})$. The beautiful
lemma yields $t_{2}a_{2}\in E(G)$ (see Figure 4.16(a)). Since $G$ is triangle-
free, $b_{1},t_{2}\in\mathrm{N}(a_{3})$ implies $b_{1}t_{2}\not\in E(G)$.
Together with Lemma 4.3 this ensures the existence of a common neighbour $q$
of $\\{a_{0},b_{1},t_{2},t_{3}\\}$ (see Figure 4.16(b)). But now the graph
$\Upsilon-a_{3}-b_{0}+q+t_{2}+t_{3}$ drawn in Figure 4.16(c) has no
independent set of size five, which contradicts $G\in\mathfrak{D}_{4}$. ∎

######  Lemma 4.14.

Let $\Upsilon\subseteq G\in\mathfrak{D}_{4}$ and let $a_{1}^{\prime}$ be an
$\Upsilon$-twin of $a_{1}$. If
$t_{2}^{\prime}\in\mathrm{Ext}(\Upsilon(a_{1}^{\prime}),a_{2})$ and there
exists a common neighbour of $a_{1}$, $b_{1}$, $t_{2}^{\prime}$, then $a_{0}$
is reliable (with respect to $\Upsilon$).

$c$$a_{2}$$a_{3}$$a_{4}$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$t_{2}^{\prime}$$a_{1}^{\prime}$$q$$t_{0}$
(a)

$a_{4}$$a_{3}$$a_{1}^{\prime}$$b_{2}$$b_{1}$$c$$t_{2}^{\prime}$$b_{4}$$b_{0}$$a_{1}$$b_{3}$$t_{0}$
(b)

$a_{4}$$a_{3}$$z$$b_{2}$$b_{1}$$c$$t_{2}^{\prime}$$b_{4}$$t_{0}$$q$$b_{0}$$a_{1}$
(c)

Figure 4.17. The proof of Lemma 4.14.

###### Proof.

Let $q$ be a common neighbour of $\\{a_{1},b_{1},t_{2}^{\prime}\\}$ and assume
for the sake of contradiction that there exists some
$t_{0}\in\mathrm{Ext}(\Upsilon,a_{0})$, so that
$a_{1},a_{4},b_{0}\in\mathrm{N}(t_{0})$ (see Figure 4.17(a)). Since the only
independent set of size five in the graph $\Upsilon-
a_{0}-a_{2}+a_{1}^{\prime}+t_{0}+t_{2}^{\prime}$ drawn in Figure 4.17(b) is
$\\{b_{3},b_{4},c,t_{0},t_{2}^{\prime}\\}$, property $\mathcal{D}_{4}$
guarantees the existence of a common neighbour $z$ of this set. But now the
graph $\Upsilon-a_{0}-a_{2}-b_{3}+t_{0}+t_{2}^{\prime}+q+z$ drawn in Figure
4.17(c) has no independent set of size five, contrary to
$G\in\mathfrak{D}_{4}$. ∎

###  4.4. Independent sets

Let us now return to Vega graphs and study their independent subsets. An
independent set $T\subseteq V(\Upsilon^{\mu\nu}_{i})$ is said to be small if
it intersects $\\{x,y\\}$ and two of the sets
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\Gamma_{\mathrm{green}}}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}$.
So if $\mu=1$, then all small sets contain $x$. We proceed with a
classification of independent sets.

######  Lemma 4.15.

If $T\subseteq V(\Upsilon_{i}^{\mu\nu})$ is independent, then one of the
following six cases occurs.

  1. ( )

There is a vertex of $V(\Upsilon_{i}^{\mu\nu})$ whose neighbourhood contains
$T$;

  2. ( )

$\mu=1$ and
$\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}\\}\subseteq
T\subseteq\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w},x\\}$;

  3. ( )

$\nu=1$ and
$\\{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b,v},{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}\\}\subseteq
T\subseteq{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\\{b,v\\}}\cup{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}$;

  4. ( )

$\\{{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c,w},{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}\\}\subseteq
T\subseteq{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\\{c,w\\}}\cup{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}$;

  5. ( )

$\nu=0$ and
$\\{{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c,w},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}\\}\subseteq
T\subseteq{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\\{c,w\\}}\cup{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\Gamma_{\mathrm{green}}}$;

  6. ( )

$T$ is small.

###### Proof.

A vertex $q\in V(\Upsilon_{i}^{\mu\nu})$ is said to govern $T$ if
$T\subseteq\mathrm{N}(q)$. Let $\Phi$ be the set of colours $\varphi$
satisfying $T\cap\Gamma_{\varphi}\neq\varnothing$. It is easily seen that
$|\Phi|=3$ is impossible. If $|\Phi|=2$ there is a vertex $j\in\Gamma_{i}$
such that $T\cap\Gamma_{i}\subseteq\mathrm{N}(j)$ and either $j$ governs $T$
or $T$ is small. We may henceforth suppose that $|\Phi|\leq 1$.

Next, let $\Psi$ be the set of colours of the vertices in
$T\cap\mathcal{C}_{6}$. If $|\Psi|=3$ and neither $x$ nor $y$ governs $T$,
then ( ) ‣ 4.15 holds. If $|\Psi|=2$, then $T\cap\mathcal{C}_{6}$ consists of
two vertices and the vertex between them governs $T$. If $|\Psi|\leq 1$ and,
moreover, $|T\cap\mathcal{C}_{6}|\leq 1$, then there is a hexagonal vertex
governing $T$. In all remaining cases $T\cap\mathcal{C}_{6}$ is a pair of
vertices of the same colour.

But if
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\\{a,u\\}}\subseteq
T$, then one of
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}$
governs $T$ (depending on whether the vertices in $T\cap\Gamma_{i}$ are green
or blue). Similarly, if
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\\{b,v\\}}\subseteq
T$ and none of
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-2}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$
governs $T$, then ( ) ‣ 4.15 holds. Finally, if
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\\{c,w\\}}\subseteq
T$ and none of
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}3i-2}$
governs $T$, then ( ) ‣ 4.15 or ( ) ‣ 4.15 holds. ∎

In the remainder of this subsection we study situations where
$\Upsilon^{\mu\nu}_{i}\subseteq G\in\mathfrak{D}_{4}$ and for some $q\in V(G)$
the set $\mathrm{N}(q)\cap V(\Upsilon_{i}^{\mu\nu})$ is in one of the cases (
) ‣ 4.15 – ( ) ‣ 4.15. We begin with a couple of simple applications of the
cube lemma.

######  Lemma 4.16.

Let $\Upsilon_{i}^{\mu\nu}\subseteq G\subseteq\mathfrak{D}_{4}$ and $q\in
V(G)$.

  1. ( )

If
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}\in\mathrm{N}(q)$,
then $x\in\mathrm{N}(q)$.

  2. ( )

If
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}\in\mathrm{N}(q)$
and $\mu=0$, then $y\in\mathrm{N}(q)$.

###### Proof.

Part ( ) ‣ 4.16 follows from the fact that the cube

$(Q)$ |  | $q$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$
---|---|---|---
$x$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$

cannot be induced. By $\sigma$-symmetry part ( ) ‣ 4.16 holds as well. ∎

######  Lemma 4.17.

Suppose $\Upsilon_{i}^{\mu\nu}\subseteq G\in\mathfrak{D}_{4}$ and that $q\in
V(G)$ is adjacent to
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$.

  1. ( )

If
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}\in\mathrm{N}(q)\cap{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}$,
then
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}[0,j]}\subseteq\mathrm{N}(q)$.

  2. ( )

If
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j}\in\mathrm{N}(q)\cap{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}$,
then
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}[j,3i-2]}\subseteq\mathrm{N}(q)$.

###### Proof.

For the proof of part ( ) ‣ 4.17 we consider any
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}t}\in{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}[0,j)}$
and look at the cube

$(Q)$ |  | $q$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}t+i}$
---|---|---|---
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}t}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}$

.

Since $(Q)$ is not induced and
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(t+i)}\not\in
E(G)$, we have indeed
$q{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}t}\in
E(G)$. Similarly, to prove part ( ) ‣ 4.17, we observe that for given
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}t}\in{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}(j,3i-2]}$
the facts that the cube

$(Q)$ |  | $q$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}t-i}$
---|---|---|---
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}t}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j}$

is not induced and
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(t-i)}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j}\not\in
E(G)$ yield the edge
$q{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}t}\in
E(G)$. ∎

######  Corollary 4.18.

If $\Upsilon_{i}^{\mu 1}\subseteq G\in\mathfrak{D}_{4}$ and some $q\in V(G)$
is adjacent either to
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}$
or to
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$,
then $G$ has a subgraph isomorphic to $\Upsilon_{i}^{\mu 0}$.

###### Proof.

Because of the automorphism $\tau_{1}$ it suffices to treat the case
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v},{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}\in\mathrm{N}(q)$
(recall that
$\tau_{1}({\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c})={\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$,
$\tau_{1}({\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w})={\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$,
$\tau_{1}({\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0})={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}$).
Lemma 4.17( ) ‣ 4.17 yields
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}\subseteq\mathrm{N}(q)$
and, therefore, $q$ can play the rôle of
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$.
∎

######  Lemma 4.19.

Let $\Upsilon_{i}^{\mu\nu}\subseteq G\in\mathfrak{D}_{4}$ and let $q\in V(G)$
be adjacent to
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$.

  1. ( )

If
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}\in\mathrm{N}(q)\cap{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}$,
then
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}[j,i-1]}\subseteq\mathrm{N}(q)$.

  2. ( )

If
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j}\in\mathrm{N}(q)\cap{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\Gamma_{\mathrm{green}}}$,
then
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}[i,j]}\subseteq\mathrm{N}(q)$.

###### Proof.

As in the proof of Lemma 4.17 we consider any vertices
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}t}\in{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}(j,i-1]}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}s}\in{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}[i,j)}$
and look at the cubes

| $(Q)$ |  | $q$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}t-i}$
---|---|---|---
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}t}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}$
and |  | $(Q)$ |  | $q$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}s+i}$
---|---|---|---
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}s}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j}$

,

respectively. ∎

######  Lemma 4.20.

Let $\Upsilon_{i}^{\mu\nu}\subseteq G\in\mathfrak{D}_{4}$ and let $q\in V(G)$
be adjacent to
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$.

  1. ( )

If
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j}\in\mathrm{N}(q)\cap{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\Gamma_{\mathrm{green}}}$,
then
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}[j,2i-1-\nu]}\subseteq\mathrm{N}(q)$.

  2. ( )

If
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j}\in\mathrm{N}(q)\cap{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}$,
then
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}[2i,j]}\subseteq\mathrm{N}(q)$.

###### Proof.

Arguing similarly again, we consider any vertices
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}t}\in{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(j,2i-1-\nu]}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}s}\in{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}[2i,j)}$
and look at the cubes

| $(Q)$ |  | $q$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}t-i}$
---|---|---|---
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}t}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j}$
and |  | $(Q)$ |  | $q$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}s+i}$
---|---|---|---
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}s}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j}$

,

respectively. ∎

######  Lemma 4.21.

If $\Upsilon_{i}^{\mu 0}\subseteq G\in\mathfrak{D}_{4}$ and some vertex $q\in
V(G)$ is adjacent to either
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$
or to
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$,
then $G$ contains a subgraph isomorphic to $\Upsilon_{i+1}^{\mu 1}$.

s${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$$q$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$
(a)

${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}a}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}b}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}u}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}v}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}w}$$x$missingvertex$2i-1$$i$$i-1$$0$$q$$2i$$3i-2$$z$
(b)

${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}b}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}c}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}a}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}w}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}u}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}v}$$x$missingvertex$i-1$$0$$3i-2$$2i$$q$$z$$i$$2i-1$
(c)

Figure 4.18. The proof of Lemma 4.21.

###### Proof.

Since $\tau_{0}$ fixes
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$
and exchanges
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$,
it suffices to treat the case
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w},{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}\in\mathrm{N}(q)$.
Lemma 4.19( ) ‣ 4.19 yields
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}\subseteq\mathrm{N}(q)$.
By $\mathcal{D}_{2}$ applied to the hexagon
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v(2i-1)b}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}q{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$
(see Figure 4.18(a)) there exists a vertex $z$ adjacent to either
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$
or to
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$,
$q$.

In the former case Lemma 4.19( ) ‣ 4.19 yields
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\Gamma_{\mathrm{green}}}\subseteq\mathrm{N}(z)$
and the desired copy of $\Upsilon^{\mu 1}_{i+1}$ is shown, with the possible
exception of $y$, in Figure 4.18(b).

So we can henceforth assume
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v},q\in\mathrm{N}(z)$.
Notice that
$q{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}$
cannot be an edge of $G$, since otherwise $G$ contained the triangle
$q{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}$.
Next, the cube

$(Q)$ |  | $z$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}$
---|---|---|---
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$ | $q$

cannot be induced, whence
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i}\in\mathrm{N}(z)$.
Now Lemma 4.17( ) ‣ 4.17 tells us
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}\subseteq\mathrm{N}(z)$
and it remains to look at Figure 4.18(c). ∎

Recall that an independent set $T\subseteq V(\Upsilon_{i}^{\mu\nu})$ is said
to be small and if it intersects $\\{x,y\\}$ and two of the three sets
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\Gamma_{\mathrm{green}}}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}$.
Since $T$ cannot intersect all three of them, there is a unique colour
$\varphi\in\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\mathrm{red}},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\mathrm{green}},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\mathrm{blue}}\\}$
such that $T\cap\Gamma_{\varphi}=\varnothing$; we call $\varphi$ the colour of
$T$. Due to $\sigma$-symmetry it usually suffices to consider small sets
containing $x$.

Given a Vega graph $\Upsilon_{i}^{\mu\nu}$ we write
$\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$ for the class of graphs in
$\mathfrak{D}_{4}$ that contain $\Upsilon_{i}^{\mu\nu}$ but no larger Vega
graph, i.e., no Vega graph $\Upsilon^{\mu^{\prime}\nu^{\prime}}_{i^{\prime}}$
with more vertices than $\Upsilon_{i}^{\mu\nu}$. Eventually we shall show shat
if $\Upsilon_{i}^{\mu\nu}\subseteq
G\in\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$, then there is no $q\in V(G)$
such that $\mathrm{N}(q)\cap V(\Upsilon_{i}^{\mu\nu})$ is small. In the
special case $i=2$ this can often be inferred from earlier results using
exceptional isomorphisms.

######  Lemma 4.22.

If $\Upsilon_{2}^{\mu\nu}\subseteq
G\in\mathfrak{D}_{4}(\Upsilon_{2}^{\mu\nu})$, $q\in V(G)$, and
$T=\mathrm{N}(q)\cap V(\Upsilon_{i}^{\mu\nu})$ is small, then $\mu=\nu=0$ and
$T$ is red or green.

###### Proof.

By $\sigma$-symmetry it suffices to consider the case $x\in T$. Suppose first
that $T$ is blue, whence
$T\supseteq\\{x,{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}\\}$.

${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$$x$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}3}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$$y$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$$\varrho$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}$$x$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$$0$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$$y$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}3}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}$
Figure 4.19. The isomorphism $\varrho$.

Recall, that the exceptional isomorphism $\varrho$ introduced in §4.1 maps
$\Upsilon_{2}^{\mu\nu}$ onto $\Upsilon_{2}^{\nu\mu}$ and the three vertices
$x$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}$
to
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$
(see Figure 4.19). In the sequel such situations will be written as

$(\Upsilon_{2}^{\mu\nu},\\{x,{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}\\})\cong(\Upsilon_{2}^{\nu\mu},\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}\\})\qquad(\textrm{via
}\varrho)\,.$

Depending on whether $\mu=1$ or $\mu=0$ we now get a contradiction to
$G\in\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$ from Corollary 4.18 or Lemma
4.21.

Suppose next that $T$ is red, which implies
$\\{x,{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}3},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}\\}\subseteq
T$ and, therefore, $\nu=0$. If, in addition, $\mu=1$, then

$\displaystyle(\Upsilon_{2}^{10},\\{x,{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}3},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}\\})$
$\displaystyle\cong(\Upsilon_{2}^{01},\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0},y,{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}\\})\qquad(\textrm{via
}\varrho)$
$\displaystyle\cong(\Upsilon_{2}^{01},\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1},x,{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}\\})\qquad(\textrm{via
}\sigma\circ\tau_{1})$

reduces the current situation to the blue case, which has already been dealt
with. Thus we have indeed $\mu=\nu=0$. Finally, the case that $T$ is green
reduces to the earlier ones by $\tau_{\nu}$-symmetry. ∎

By an auxiliary path in $\Upsilon_{i}^{\mu\nu}$ we mean a path of length three
in $\Gamma_{i}$ whose first and last vertex have the same colour, also called
the colour of the path. For instance, if $j$, $j+1$ are consecutive vertices
of the same colour $\varphi$, then

$\pi_{j}=j-(j+i)-(j+2i)-(j+1)$

is an auxiliary path whose colour is $\varphi$. So every Vega graph
$\Upsilon_{i}^{\mu\nu}$ possesses a red auxiliary path
$\pi_{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}}={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}-{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}-{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i}-{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}$.
If $i\geq 3$ there is for every vertex of $\Gamma_{i}$ an auxiliary path
starting in that vertex and, in particular, there are auxiliary paths of all
colours. Every auxiliary path $\pi$ in $\Upsilon_{i}^{\mu\nu}$ gives rise to a
copy $\Upsilon(\pi)$ of the Mycielski-Grötzsch graph in
$\Upsilon_{i}^{\mu\nu}$ (see Figure 4.20).

${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$$x$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$
(a) a red path

${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$$x$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$
(b) a green path

${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$$x$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$
(c) a blue path

Figure 4.20. A copy $\Upsilon(\pi)$ of the Mycielski-Grötzsch graph in
$\Upsilon_{i}^{\mu\nu}$.

One can learn a lot by applying the results from the previous subsection to
graphs of the form $\Upsilon(\pi)$.

######  Lemma 4.23.

If $\Upsilon_{i}^{\mu\nu}\subseteq
G\in\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$ and $q\in V(G)$, then
$\mathrm{N}(q)\cap V(\Upsilon_{i}^{\mu\nu})$ is not small.

###### Proof.

By $\sigma$\- and $\tau_{\nu}$-symmetry it suffices to show that if
$\mathrm{N}(q)$ contains $x$ and a vertex from
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\Gamma_{\mathrm{green}}}$,
then it is disjoint to
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}\cup{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}$.

First case:
$\mathrm{N}(q)\cap{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}[i,2i-2]}\neq\varnothing$.

In the special case $i=2$ this means
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2}\in\mathrm{N}(q)$.
Since $G$ is triangle-free, $q$ cannot have a neighbour in
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}$
and by Lemma 4.22 there are no neighbours of $q$ in
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}$
either. Suppose next that $i\geq 3$, so that the interval
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}[i,2i-2]}$
consists of more than one vertex. Thus there exists a pair of consecutive
vertices
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\\{m,m+1\\}}\subseteq{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}[i,2i-2]}$
such that
$\mathrm{N}(q)\cap{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}\\{m,m+1\\}}\neq\varnothing$.
Working with the auxiliary path

$\pi_{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}}={\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}-{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}(m+i)}-{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}(m-i+1)}-{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(m+1)}$

we construct the graph
$\Upsilon(\pi_{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}})$
(see Figure 4.21(a)). The blue vertex
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}m+1+i}$
is adjacent to
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m+1}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$
and, therefore,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}$
is unreliable in
$\Upsilon(\pi_{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}})$.
Similarly, the red vertex
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}m-i}$
exemplifies the unreliability of
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m+1}$.
Now Lemma 4.13 tells us that
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$
and
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$
are reliable. In particular, $q$ is neither in
$\mathrm{Ext}(\Upsilon(\pi_{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}}),{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u})$
nor in
$\mathrm{Ext}(\Upsilon(\pi_{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}}),{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w})$
and Lemma 4.10 implies that $q$ is an
$\Upsilon(\pi_{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}})$-twin
of
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$.
Thus $q$ is adjacent to
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$
and, consequently, to no vertex in
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}\cup{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}$.

${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$$x$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}m+i}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}m-i+1}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m+1}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}$
(a)
$\Upsilon(\pi_{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}})$

${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$$x$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}m}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}$
(b) $\Upsilon(\omega)$

${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$$x$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}$
(c) $\Upsilon(\varpi)$

Figure 4.21. The proof of Lemma 4.23.

Second case: We have $\nu=0$ and
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}\in\mathrm{N}(q)$.

Due to
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}\Gamma_{\mathrm{red}}}\subseteq\mathrm{N}({\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1})$
we only need to derive a contradiction from the assumption that there exists
some blue
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}m}\in\mathrm{N}(q)\cap{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}$.
To this end we consider the green auxiliary path
$\omega={\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}-{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}m}-{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}(i-1)}-{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(2i-1)}$
(see Figure 4.21(b)) and the associated graph $\Upsilon(\omega)$. The vertices
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$
and $q$ witness that
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$
and
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$
are unreliable; so $x$ is reliable by Lemma 4.13 or, in other words, $\mu=1$.
Now Lemma 4.22 tells us that $i\geq 3$.

Next we apply Lemma 4.14 for the green auxiliary path
$\varpi={\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}-{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i}-{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1}-{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(2i-1)}$
to $\Upsilon(\varpi)$ with the labelling
$a_{0}={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$,
$a_{1}={\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$,
$a_{2}={\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}$,
$b_{1}={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$
and the additional vertices
$a_{1}^{\prime}={\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i+1}$,
$t_{2}^{\prime}={\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i+1}$.
As
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}2}$
is a common neighbour of
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}2i+1}$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$,
we infer that
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$
is reliable. Together with
$x,{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}\in\mathrm{N}(q)$
and Lemma 4.10 this entails that $q$ is an $\Upsilon(\varpi)$-twin of
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$.
But now
$q{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}wm}$
is a triangle in $G$, which is absurd. ∎

######  Corollary 4.24.

If $\Upsilon_{i}^{\mu\nu}\subseteq
G\in\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$ and $\pi$ denotes an auxiliary
path in $\Upsilon_{i}^{\mu\nu}$ with colour $\varphi$, then those among
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$
whose colour is not $\varphi$ are reliable in $\Upsilon(\pi)$.

###### Proof.

Otherwise there existed a vertex $q\in V(G)$ for which $\mathrm{N}(q)\cap
V(\Upsilon_{i}^{\mu\nu})$ is small (see Figure 4.20), contrary to Lemma 4.23.
∎

Summarising the work of this subsection, we can now establish a weak form of
the attachment lemma with an inclusion as opposed to an equality.

######  Lemma 4.25.

If $\Upsilon_{i}^{\mu\nu}\subseteq
G\in\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$, then for every $q\in V(G)$ there
is some $z\in V(\Upsilon_{i}^{\mu\nu})$ such that $\mathrm{N}(q)\cap
V(\Upsilon_{i}^{\mu\nu})\subseteq\mathrm{N}(z)\cap V(\Upsilon_{i}^{\mu\nu})$.

###### Proof.

If no such vertex $z$ exists, then $T=\mathrm{N}(q)\cap
V(\Upsilon_{i}^{\mu\nu})$ satisfies one of the five statements ( ) ‣ 4.15 – (
) ‣ 4.15 in Lemma 4.15. In case ( ) ‣ 4.15 Lemma 4.16( ) ‣ 4.16 yields
$T=\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w},x\\}$,
and $q$ can play the rôle of $y$ in a copy of $\Upsilon_{i}^{0\nu}$ in $G$,
which is absurd. Similarly, Corollary 4.18, Lemma 4.21, and Lemma 4.23 exclude
the remaining cases. ∎

###  4.5. The twin lemma

The goal of this subsection is to prove the twin lemma for graphs in
$\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$, which simply asserts that all these
graphs have the $\Upsilon_{i}^{\mu\nu}$-twin property. Since Vega graphs have
several different types of edges, the argument involves a case analysis. We
begin with some edges, for which the twin property can be derived from the
cube lemma alone.

Edges of a Vega graph $\Upsilon_{i}^{\mu\nu}$ that connect two vertices of
$\Gamma_{i}$ are called Andrásfai edges. Such an edge $jm$ is said to be long
if $j-m\neq\pm i$. Moreover, for $\nu=0$ the edge
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(2i-1)}$
is considered to be long as well. All other Andrásfai edges are short. As in
the previous section, long edges are easier to handle than short ones.

######  Lemma 4.26.

If $e$ denotes a long Andrásfai edge of a Vega graph $\Upsilon_{i}^{\mu\nu}$,
then every graph $G\in\mathfrak{D}_{4}$ has the
$(\Upsilon_{i}^{\mu\nu},e)$-twin property. Moreover, if $\mu=0$ the same holds
for $e=xy$.

###### Proof.

For the last statement we consider any $\Upsilon_{i}^{0\nu}$-twins
$x^{\prime}$ and $y^{\prime}$ of $x$ and $y$, respectively. Since the cube

$(Q)$ |  | $x^{\prime}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$
---|---|---|---
$y^{\prime}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$

cannot be induced, $x^{\prime}y^{\prime}$ is indeed an edge of $G$.

Now let $e=jm$ be a long Andrásfai edge. Suppose first that
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}$
is red and
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}$
is green. Due to
$i<{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}-{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}\leq
2i-1$ we have
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}\neq{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}$
and, hence, there is a green vertex
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j+i}$.
Furthermore,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}m-i}$
is red and
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(j+i)}-{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}(m-i)}=2i-(m-j)\in[i-1]$
shows
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}(m-i)}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(j+i)}\not\in
E(G)$. So if $j^{\prime}$, $m^{\prime}$ are $\Upsilon_{i}^{\mu\nu}$-twins of
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m}$,
then the cube

$(Q)$ |  | $j^{\prime}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}m-i}$
---|---|---|---
$m^{\prime}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$ | ${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j+i}$

leads to the desired edge $j^{\prime}m^{\prime}\in E(G)$.

Similarly, if
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j}$
is green and
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}m}$
is blue, then
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j}\neq{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}2i-1}$
and
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(m-i)}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}(j+i)}\not\in
E(G)$, so that we can work with the cube

$(Q)$ |  | $j^{\prime}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}m-i}$
---|---|---|---
$m^{\prime}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$ | ${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$ | ${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j+i}$

.

The remaining case, where $e$ connects a red and a blue vertex, reduces to one
of the previous two by $\tau_{\nu}$-symmetry. ∎

We proceed with short Andrásfai edges.

######  Lemma 4.27.

If $e$ denotes a short Andrásfai edge of a Vega graph $\Upsilon_{i}^{\mu\nu}$,
then every graph $G\in\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$ has the
$(\Upsilon_{i}^{\mu\nu},e)$-twin property.

###### Proof.

Suppose first that $e$ connects a red vertex with a green vertex. Recalling
that the edge
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(2i-1)}$
is regarded as being long, we can write
$e={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(j+i)}$
for some
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}\in{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}[0,i-1]}$.
We may further assume
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}\neq{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}i-1}$,
because if the edge
$e={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}(i-1)}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(2i-1)}$
exists, then $\tau_{0}$ reflects it to
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}i}$,
which corresponds to
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}0}$.

Working with the red auxiliary path
$\pi_{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}}={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}-{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(j+i)}-{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}(j+2i)}-{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}(j+1)}$
we form the graph
$\Upsilon(\pi_{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}})$
(see Figure 4.22(a)). If there are non-adjacent $\Upsilon_{i}^{\mu\nu}$-twins
$j^{\prime}$, $(j+i)^{\prime}$ of
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j+i}$,
then Lemma 4.6 applied to
$\Upsilon(\pi_{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}})$
yields a common neighbour $q$ of $j^{\prime}$, $(j+i)^{\prime}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$
(see Figure 4.10(b)). We colour $j^{\prime}$ red, $(j+i)^{\prime}$ green, $q$
blue, and construct a copy of $\Upsilon_{i+1}^{\mu\nu}$ whose Andrásfai part
is shown in Figure 4.22(b), thereby obtaining a contradiction to
$G\in\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$. The edges from
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}q}$
to
$[{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j+1},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j+i-1}]$
required here exist by Lemma 4.19 applied to
$\Upsilon_{i}^{\mu\nu}({\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j^{\prime}})$
and
$\Upsilon_{i}^{\mu\nu}({\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(j+i)^{\prime}})$.

${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$$x$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j+2i}$${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j+i}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}$${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j+1}$
(a)
$\Upsilon(\pi_{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}})$

$3i-2$$j+2i$$q$$j+2i-1$$2i$$2i-1-\nu$$i+j-1$$(i+j)^{\prime}$$i+j$$i$$0$$j$$j+1$$j^{\prime}$$i-1$
(b)

$3i-2$$j+2i$$(j+2i)^{\prime}$$j+2i-1$$2i$$2i-1-\nu$$j+i$$(j+i)^{\prime}$$j+i+1$$i$$0$$j$$j+1$$q$$i-1$
(c)

Figure 4.22. The proof of Lemma 4.27.

Next we consider the case that $e$ connects a green vertex with a blue vertex
and write
$e={\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}(j+i)}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}(j+2i)}$,
where
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}\in{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}[0,i-2]}$.
By Lemma 4.7 applied to
$\Upsilon(\pi_{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}})$
there is a common neighbour $q$ of $(j+i)^{\prime}$, $(j+2i)^{\prime}$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}$,
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$
(see Figures 4.10(c) and 4.22(a)). We colour $(j+i)^{\prime}$ green,
$(j+2i)^{\prime}$ blue, $q$ red and construct a copy of
$\Upsilon_{i+1}^{\mu\nu}$ whose Andrásfai part is shown in Figure 4.22(c). The
required edges from
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}q}$
to
$[{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}j+i+1},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j+2i-1}]$
are obtained from Lemma 4.20. So as in the previous case we reach a
contradiction to $G\in\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$.

Finally, the case that $e$ connects a red vertex to a blue vertex reduces to
the previous ones by $\tau_{\nu}$-symmetry. ∎

######  Lemma 4.28 (Twin Lemma).

Every $G\in\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$ has the
$\Upsilon_{i}^{\mu\nu}$-twin property.

###### Proof.

Let $e$ be an edge of $\Upsilon_{i}^{\mu\nu}\subseteq
G\in\mathfrak{D}_{4}(\Upsilon_{i}^{\mu\nu})$, for which we want to confirm the
twin property. For the sake of contradiction we assume that there are non-
adjacent twins of the end vertices of $e$, indicated in the usual way by
primes. Owing to the two foregoing lemmata we have
$e\cap\mathcal{C}_{6}\neq\varnothing$. Moreover, by $\sigma$-symmetry we can
suppose $y\not\in e$, which means that one of the following two main cases
occurs.

First case: $e$ connects one of
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}$,
${\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}v}$,
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}$
to $\Gamma$.

By $\tau_{\nu}$-symmetry we may assume
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}u}\in
e$ or
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w}\in
e$. If
$e={\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}uj}$,
there exists a red auxiliary path $\pi$ one of whose end vertices is
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}j}$.
By Lemma 4.6 applied to $\Upsilon(\pi)$, there exists a vertex $q$ adjacent to
$u^{\prime}$, $j^{\prime}$, $x$, and an inner vertex of $\pi$ (see Figures
4.10(b) and 4.20(a)). But this means that $q$ has a small neighbourhood in
$\Upsilon_{i}^{\mu\nu}(j^{\prime})$, contrary to Lemma 4.23.

If $i\geq 3$ the case
$e={\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}wj}$,
where
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j}\in{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}\Gamma_{\mathrm{blue}}}$,
is similar, because there exists a blue auxiliary path starting with
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j}$.
Finally, $i=2$ implies
${\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}j}={\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}$
and due to

$(\Upsilon_{2}^{\mu\nu},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}w})\cong(\Upsilon_{2}^{\nu\mu},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}4}{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}1})\qquad(\textrm{via
}\varrho)$

(see Figure 4.19) this case reduces to Lemma 4.27.

Second case:
$e\cap\\{{\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a},{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}\\}\neq\varnothing$.

If
${\color[rgb]{0.75,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0,0}a}\in
e$ we just need to apply Lemma 4.5 to $\Upsilon(\pi)$ for an appropriate red
auxiliary path $\pi$. Provided that $i\geq 3$ there exist auxiliary paths
ending in all vertices and this argument generalises. Thus it remains to
consider the case that $i=2$ and
$\\{{\color[rgb]{0,0.65,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.65,0}b},{\color[rgb]{0,0,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.75}c}\\}\cap
e\neq\varnothing$. Using our isomorphisms and automorphisms, every possibility
can be shown to be equivalent to a case that has already been covered. Indeed,
we have