# Triangle-free projective-planar graphs with diameter two: domination and
characterization 111This work is partially supported by the IFCAM project
Applications of graph homomorphisms (MA/IFCAM/18/39)

Dibyayan Chakraborty  Sandip Das  Srijit Mukherjee  Uma kant Sahoo  Sagnik Sen
Indian Institute of Science, Bengaluru  Indian Statistical Institute, Kolkata,
India  Indian Institute of Technology Dharwad, India

###### Abstract

In 1975, Plesník characterized all triangle-free planar graphs as having a
diameter $2$. We characterize all triangle-free projective-planar graphs
having a diameter $2$ and discuss some applications. In particular, the main
result is applied to calculate the analogue of clique numbers for graphs,
namely, colored mixed graphs, having different types of arcs and edges.

###### keywords:

projective-planar , forbidden minor characterization , domination number

[algorithm]capposition=top

##  1 Introduction and main results

In 1975, Plesník [1] characterized all triangle-free planar graphs222In this
article, we use the notation and terminology of “Introduction to Graph Theory”
by D. B. West [2]. having diameter $2$ by proving the following result.

######  Theorem 1 (Plesník 1975 [1]).

A triangle-free planar graph $G$ has a diameter $2$ if and only if it is
isomorphic to one of the following graphs:

  1. (i)

$K_{1,n}$ for $n\geq 2$,

  2. (ii)

$K_{2,n}$ for $n\geq 2$,

  3. (iii)

the graph $C_{5}(m,n)$ obtained by adding $(m+n)$ degree-$2$ vertices to the
$5$-cycle $C_{5}=v_{1}v_{2}v_{3}v_{4}v_{5}v_{1}$, for $m,n\geq 0$, in such a
way that $m$ of the vertices are adjacent to $v_{1},v_{3}$ and $n$ of the
vertices are adjacent to $v_{1},v_{4}$.

We prove the analogue of Plesník’s result for projective-planar graphs, that
is, graphs that can be embedded on the non-orientable surface of Euler genus
one (also known as the real projective plane) without their edges crossing
each other except, maybe, on the vertices. For convenience, let us refer to
the graphs listed in Theorem 1 as Plesník graphs.

|  |  |  |  |  |
---|---|---|---|---|---|---
(i) | (ii) | (iii) | (iv) | (v) | (vi) | (vii)
Figure 1: (i) The Petersen graph $P_{10}$, (ii) The Wagner graph $W_{8}$,
(iii) The graph $W_{8}^{+}$,(iv) The Grötzsch graph $M_{11}$, (v) The graph
$M^{-}_{11}$, (vi) The graph $M^{=}_{11}$, (vii) The graph $K^{*}_{3,4}$.

######  Theorem 2.

A triangle-free projective-planar graph $G$ has diameter $2$ if and only if it
is isomorphic to one of the following:

  1. (i)

a Plesník graph,

  2. (ii)

$K_{3,3}$ or $K_{3,4}$,

  3. (iii)

the graph $K_{3,3}(n)$ obtained by adding $(n-1)$ parallel edges
$e_{2},e_{3},\ldots,e_{n}$ to one of the edges $e_{1}$ of $K_{3,3}$ and
subdividing each $e_{i}$ exactly once for $n\geq 1$,

  4. (iv)

the graph $K_{3,4}(n)$ obtained by adding $(n-1)$ parallel edges
$e_{2},e_{3},\ldots,e_{n}$ to one of the edges $e_{1}$ of $K_{3,4}$ and
subdividing each $e_{i}$ exactly once for $n\geq 1$,

  5. (v)

one of the seven graphs depicted in Figure 1.

Let us now discuss a few more results regarding properties of graphs having
small diameters that can be embedded on a given surface $\mathbb{S}$ to place
our work into context. Since $\mathbb{S}$ has an Euler characteristic, it
follows from the Euler’s formula [3] that any graph embedded in $\mathbb{S}$
has a bounded minimum degree. This implies that if we consider such a graph
with diameter 2, then its domination number is at most its minimum degree.

In 1996, MacGillivray and Seyffarth [4] proved that planar graphs with
diameter $2$ have domination numbers at most $3$. In 2002, Goddard and Henning
[5] showed that there is exactly one planar graph having diameter $2$ that has
a domination number equal to $3$. They also proved that for each surface
(orientable or non-orientable) $\mathbb{S}$, there are finitely many graphs
having diameter $2$ and domination number at least $3$ that can be embedded in
$\mathbb{S}$. A natural question to ask in this context is the following.

######  Question 1.

Given a surface $\mathbb{S}$, can you find the list of all graphs having
diameter $2$ and domination number at least $3$ that can be embedded on
$\mathbb{S}$?

As we just mentioned, Goddard and Henning [5] answered Question 1 when
$\mathbb{S}$ is the sphere (or equivalently, the Euclidean plane). However, it
seems that the question can be very difficult to answer in general as the
tight upper bounds on the domination number for a family of graphs that can be
embedded on a surface, other than the sphere, is yet to be found. Therefore,
it makes sense to ask the following natural restriction instead.

######  Question 2.

Given a surface $\mathbb{S}$, can you find the list of all triangle-free
graphs having a diameter $2$ and domination number at least $3$ that can be
embedded on $\mathbb{S}$?

Notice that, Plesník’s characterization implies that the answer for Question 2
is the empty list when $\mathbb{S}$ is the sphere. On the other hand, the
following immediate corollary of Theorem 2 answers the question when
$\mathbb{S}$ is the projective plane, along with implying that the domination
number of triangle-free projective-planar graphs having diameter $2$ is at
most three (following our earlier discussions on Euler’s characteristic). Note
that the domination number of graphs shown in Figure 1 is three.

######  Theorem 3.

Let $G$ be a triangle-free projective-planar graph having a diameter $2$. Then

  1. (a)

The domination number $\gamma(G)$ of $G$ is at most $3$.

  2. (b)

If $\gamma(G)=3$, then $G$ is isomorphic to one of the seven graphs depicted
in Figure 1.

As Theorem 3 follows directly from Theorem 2, we will focus on proving Theorem
2. This is done in Section 2. In Section 3, we provide some direct
implications of our results in determining the absolute clique number of the
families of triangle-free projective-planar graphs, which is an important
parameter in the theory of homomorphisms of colored mixed graphs333The related
definitions are deferred to Section 3..

##  2 Proof of Theorem 2

It is known, due to Euler’s formula [3] for projective-planar graphs, that any
triangle-free projective-planar graph $G$ has minimum degree $\delta(G)\leq
3$. Therefore, any triangle-free projective-planar graph having a diameter $2$
has a domination number at most $3$.

Notice that as the family of projective-planar graphs is minor-closed, due to
The Graph Minor Theorem [6], there exists a finite set $\mathcal{S}$ of graphs
such that a graph $G$ is projective-planar if and only if $G$ does not contain
a minor from $\mathcal{S}$. Actually, an explicit description of the set
$\mathcal{S}$ is provided in [7] (see [3]) and it contains $35$ graphs.
However, we will not need the full list for our proof - to be precise, we will
use only three graphs from that list: (1) $K_{3,5}$, (2) $K_{4,4}^{-}$, i.e.,
the graph obtained from $K_{4,4}$ by deleting exactly one edge, and (3) the
graph $F_{0}$ depicted in Figure 2.

|  |  |
---|---|---|---
(a) | (b) | (c) | (d)
Figure 2: The graphs (a) $F_{0}$, (b) $F_{1}$, (c) $F_{2}$, and (d) $F_{3}$
form the graph family $\mathcal{D}^{\prime}$.

######  Observation 1 ([7]; see [3]).

The graphs $K_{3,5}$, $K_{4,4}^{-}$, and $F_{0}$ are not projective-planar.

Thus any graph containing $K_{3,5}$, $K_{4,4}^{-}$, or $F_{0}$ as a minor is
not projective-planar as well. Even though the previous statement is obvious,
we will present it as another observation as it will be frequently used in our
proofs.

######  Observation 2 ([7]; see [3]).

If $G$ contains $K_{3,5}$, $K_{4,4}^{-}$, or $F_{0}$ as a minor, then $G$ is
not a projective-planar graph.

Now we get into the more technical part of our proof. First of all, for
convenience, let us denote the family of all triangle-free projective-planar
graphs having diameter $2$ by $\mathcal{PP}_{2}$. Therefore, what we are
trying to do here is to provide a list of all graphs in $\mathcal{PP}_{2}$. We
already know that if $G\in\mathcal{PP}_{2}$, then its minimum degree
$\delta(G)$ is at most $3$. We will use this as the basis of our case
analysis. Observe that any $G\in\mathcal{PP}_{2}$ is connected. Therefore, the
logical first step is to handle the graphs having a degree one vertex.

###  2.1 Characterizing graphs in $\mathcal{PP}_{2}$ having minimum degree at
most $2$

######  Lemma 1.

If $\delta(G)=1$ for a graph $G\in\mathcal{PP}_{2}$, then $G$ is isomorphic to
$K_{1,n}$ for some $n\geq 2$.

###### Proof.

Let $v$ be a degree-$1$ vertex in $G$ having $v_{1}$ as its only neighbor. As
$G$ has diameter $2$, $v_{1}$ must be adjacent to all the vertices in
$V(G)\setminus\\{v,v_{1}\\}$. Moreover, as $G$ is triangle-free, the set of
all neighbors $N(v_{1})$ of $v_{1}$ is an independent set. ∎

The next natural step is to consider the graphs having minimum degree equal to
$2$.

######  Lemma 2.

If $\delta(G)=2$ for a graph $G\in\mathcal{PP}_{2}$, then $G$ is isomorphic to
$K_{2,n+2}$, $C_{5}(m,n)$, $K_{3,4}(n)$, or $K_{3,3}(n)$ for some $m,n\geq 0$.

###### Proof.

Let $v$ be a degree-$2$ vertex having $N(v)=\\{v_{1},v_{2}\\}$. Let

$C=(N(v_{1})\cap N(v_{2}))\setminus\\{v\\}\text{ and
}S_{i}=N(v_{i})\setminus(C\cup\\{v\\})$

for $i\in\\{1,2\\}$.

$S_{1}\cup S_{2}$ induces a complete bipartite graph (else the end vertices of
any non-edge would be at a distance greater than $2$, a contradiction) and as
$\delta(G)\geq 2$, both sets are nonempty.

If $|S_{1}|\geq|S_{2}|\geq 3$, then we find a $K^{-}_{4,4}$ by taking the
graph induced by $S_{1}\cup S_{2}\cup\\{v_{1},v_{2}\\}$. This is a
contradiction due to Observation 2. Thus we must have $|S_{2}|\leq 2$.

If $|S_{2}|=2$, then $|S_{1}|\leq 3$ as otherwise we can contract the edge
$vv_{1}$ to find a $K_{3,5}$ induced by $S_{1}\cup
S_{2}\cup\\{v_{1},v_{2}\\}$. This is a contradiction due to Observation 2.

Now observe that $|S_{1}|=3$ and $|S_{2}|=2$ implies $G$ is isomorphic to
$K_{3,4}(n)$, where $n=|C|+1$. Similarly, $|S_{1}|=2$ and $|S_{2}|=2$ implies
$G$ is isomorphic to $K_{3,3}(n)$, where $n=|C|+1$.

If $|S_{2}|=1$, $|S_{1}|$ can have any value greater than or equal to $1$. In
this case, $G$ is isomorphic to $C_{5}(m,n)$, where $m=|C|$ and $n=|S_{1}|-1$.
∎

###  2.2 Characterizing graphs in $\mathcal{PP}_{2}$ that are $3$-regular

This leaves us with the final case: considering the graphs having minimum
degree equal to $3$. We break this case into two parts, namely, when $G$ is
$3$-regular and when $G$ is not $3$-regular, and tackle them separately. Also
we will use some new terminologies.

A vertex $u$ reaches a vertex $v$ if they are adjacent or they have a common
neighbor. In particular, if $w$ is a common neighbor of $u$ and $v$, then we
use the term $u$ reaches $v$ via $w$.

######  Lemma 3.

If a $3$-regular graph $G\in\mathcal{PP}_{2}$, then $G$ is isomorphic to
either $K_{3,3}$ or $W_{8}$ or $P_{10}$.

###### Proof.

Let $v\in V(G)$ be any vertex having neighbors $\\{v_{1},v_{2},v_{3}\\}$.
Moreover, let $S_{i}$ denote the set of vertices in $G\setminus\\{v\\}$ which
are adjacent to exactly $i$ vertices among $\\{v_{1},v_{2},v_{3}\\}$. Note
that, as $G$ has diameter $2$, every vertex in
$G\setminus\\{v,v_{1},v_{2},v_{3}\\}$ belongs to exactly one of $S_{1},S_{2},$
and $S_{3}$.

Observe that as $G$ is $3$-regular, we must have $|S_{3}|\leq 2$. Moreover, if
$|S_{3}|=2$, then $G$ is isomorphic to $K_{3,3}$.

If $|S_{3}|=1$, then note that we must have $|S_{2}|\leq 1$ as otherwise, it
will force one of the vertices among $\\{v_{1},v_{2},v_{3}\\}$ to have at
least two neighbors in $S_{2}$, and hence have at least four neighbors in $G$,
contradicting the $3$-regularity of $G$.

Furthermore, if $|S_{3}|=|S_{2}|=1$, then without loss of generality we may
assume that $S_{2}=\\{u\\}\subseteq N(v_{1})\cap N(v_{2})$. Thus $u$ must
reach $v_{3}$ via some vertex $u^{\prime}\in S_{1}\cap N(v_{3})$. Now each
vertex among $\\{v_{1},v_{2},v_{3}\\}$ already has three neighbors and thus
there cannot be any other vertex in $G$. Also all vertices except $u^{\prime}$
have degree $3$ at present. Thus the $3$-regularity of $G$ forces us to
include a new vertex adjacent to $u^{\prime}$ in the graph, a contradiction.
Therefore, $G$ cannot have $|S_{3}|=|S_{2}|=1$.

Thus if $|S_{3}|=1$, then we must have $S_{2}=\emptyset$. However, due to the
$3$-regularity of $G$, each vertex among $\\{v_{1},v_{2},v_{3}\\}$ has exactly
one neighbor in $S_{1}$. Let us assume that the neighbors of $v_{1},v_{2},$
and $v_{3}$ in $S_{1}$ are $w_{1},w_{2},$ and $w_{3}$, respectively. Now, as
each vertex among $\\{v_{1},v_{2},v_{3}\\}$ already has three neighbors, there
cannot be any other vertex in $G$. In fact, each vertex of $G$ other than
$w_{1},w_{2},$ and $w_{3}$ has degree $3$ already. Thus $w_{1},w_{2},$ and
$w_{3}$ must reach all of $v_{1},v_{2},$ and $v_{3}$ either directly or via
themselves. That forces $w_{1},w_{2},$ and $w_{3}$ to create a triangle,
contradicting the triangle-free property of $G$. Therefore, $G$ cannot have
$|S_{3}|=1$.

Now let us consider the situation where $|S_{3}|=0$. First observe that
$|S_{2}|\leq 3$ in this case, as otherwise one vertex among
$\\{v_{1},v_{2},v_{3}\\}$ has degree at least $4$.

If $|S_{2}|=3$, then without loss of generality, we may assume that
$S_{2}=\\{u_{1},u_{2},u_{3}\\}$ where $u_{i}\in S_{2}\setminus N(v_{i})$ for
all $i\in\\{1,2,3\\}$. Now, as every vertex among $\\{v_{1},v_{2},v_{3}\\}$
already has three neighbors each, there cannot be any other vertex in $G$.
Hence $S_{1}=\emptyset$. Thus, in particular, the vertex $u_{1}$ must reach
$v_{1}$ via some vertex of $S_{2}$. That will create a triangle, a
contradiction. So $|S_{2}|\leq 2$.

If $|S_{2}|=2$ with $S_{2}=\\{u_{1},u_{2}\\}$, then without loss of
generality, assume that $v_{3}$ is a common neighbor of $u_{1}$ and $u_{2}$.
Moreover, the sum of the degrees of $v_{1},v_{2},$ and $v_{3}$ at the moment
is $7$ and therefore we must have exactly two more vertices in $G$. Thus,
$|S_{1}|=2$ and we may assume that $S_{1}=\\{w_{1},w_{2}\\}$. Observe that
$u_{1}$ and $u_{2}$ must have exactly one neighbor each in $S_{1}$ as they
cannot be adjacent to each other in order to avoid creating a triangle. This
implies that there are exactly two edges between the sets $S_{1}$ and $S_{2}$.
Thus at least one vertex of $S_{1}$ does not have degree $3$ unless $w_{1}$
and $w_{2}$ are adjacents. Hence $w_{1}$ and $w_{2}$ must be adjacent. This
implies that $w_{1}$ and $w_{2}$ do not have a common neighbor. Therefore,
without loss of generality, we may assume that $w_{i}$ and $u_{i}$ are
adjacent to $v_{i}$ for all $i\in\\{1,2\\}$. Hence the edges $u_{1}w_{2}$ and
$u_{2}w_{1}$ are in $G$. Observe that $G$ is isomorphic to $W_{8}$ in this
case.

We have a total of nine vertices, not possible for a 3-regular graph (as nine
is an odd number).

If $|S_{2}|=0$, then each $v_{i}$ has exactly two neighbors $w_{i}$ and
$w^{\prime}_{i}$ in $S_{1}$ for all $i\in\\{1,2,3\\}$. Without loss of
generality, $w_{1}$ reaches $v_{2}$ and $v_{3}$ via $w_{2}$ and $w_{3}$,
respectively. As $w_{1}$ already has three neighbors, $w^{\prime}_{2}$ and
$w^{\prime}_{3}$ must reach $v_{1}$ via $w^{\prime}_{1}$. Note that, $w_{2}$
cannot reach $v_{3}$ via $w_{3}$ in order to avoid a triangle. Therefore,
$w_{2}$ reaches $v_{3}$ via $w^{\prime}_{3}$. Similarly, $w_{3}$ reaches
$v_{2}$ via $w^{\prime}_{2}$. This implies that $G$ is isomorphic to $P_{10}$.
∎

###  2.3 Characterizing not regular graphs in $\mathcal{PP}_{2}$ having
minimum degree $3$

Finally, the case where $\delta(G)=3$ and $\Delta(G)\geq 4$ is handled. The
proof of Lemma 4 is lengthy; in order to make the proof easier to follow, we
have divided it into several claims and lemmas and presented it in a separate
subsection.

######  Lemma 4.

If $\delta(G)=3$ and $\Delta(G)\geq 4$ for a graph $G\in\mathcal{PP}_{2}$,
then $G$ is isomorphic to $K_{3,4}$, $K_{3,4}^{+}$, $W^{+}_{8}$, $M_{11}$,
$M_{11}^{-}$, or $M_{11}^{=}$.

We will begin by presenting some basic conventions to be used throughout this
section.

####  2.3.1 Conventions used in the proof of Lemma 4

Let $v\in V(G)$ be a vertex with maximum degree and let
$N(v)=\\{v_{1},v_{2},v_{3},v_{4}\\}\cup X$ where $X$ may or may not be
$\emptyset$. Moreover, let $S_{i}$ denote the set of vertices in
$G\setminus\\{v\\}$ which are adjacent to exactly $i$ vertices among
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ (see Figure 3). Furthermore, let $m_{2}$ be
the cardinality of a maximum matching in $S_{2}$.

####  2.3.2 Basic structural properties

The proof of Lemma 4 runs via a series of claims and lemmas. In the case of
the claims, we always assume that $\delta(G)=3$ and $d(v)=\Delta(G)\geq 4$ for
a graph $G\in\mathcal{PP}_{2}$.

Figure 3: Illustrations of our convention

This brings us to our first two observations.

######  Claim 1.

A vertex in $S_{3}\cup S_{4}$ is not adjacent to a vertex in $S_{2}\cup
S_{3}\cup S_{4}.$

###### Proof.

Any vertex in $S_{4}\cup S_{3}$ has at least one neighbor in common with any
vertex in $S_{2}\cup S_{3}\cup S_{4}$. Hence, any edge between $S_{4}\cup
S_{3}$ and $S_{2}\cup S_{3}\cup S_{4}$ will create a triangle. ∎

######  Claim 2.

The value of $|S_{4}|+|S_{3}|+m_{2}$ is at most $2$.

###### Proof.

Observe that each vertex of $S_{3}$ reaches three of the four vertices among
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ directly and one of them via a vertex of
$S_{1}$ (by Claim 1). Therefore, if we contract all the edges between
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ and $S_{1}$, then each vertex of $S_{3}$
becomes adjacent to every vertex of $\\{v_{1},v_{2},v_{3},v_{4}\\}$. Moreover,
suppose there is an edge having both its end vertices in $S_{2}$, then these
end vertices cannot have a common neighbor, else a triangle is induced.
Contracting this edge, the new resulting vertex will correspond to a vertex
adjacent to each of $\\{v_{1},v_{2},v_{3},v_{4}\\}$. Therefore, if
$|S_{4}|+|S_{3}|+m_{2}\geq 3$, then $G$ will contain a $K_{4,4}$-minor. ∎

Therefore, in particular, the above claim implies that $|S_{4}|+|S_{3}|\leq
2$. This bound will be the basis of our case study.

####  2.3.3 Case: $|S_{4}|+|S_{3}|=2$

######  Claim 3.

If $|S_{4}|+|S_{3}|=2$, then $S_{2}=\emptyset$.

###### Proof.

Recall that each vertex of $S_{3}$ reaches three of the four vertices among
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ directly and one of them via a vertex of
$S_{1}$ (by Claim 1). If $|S_{4}|+|S_{3}|=2$, then $m_{2}=0$ (by Claim 2). Now
if $S_{2}\neq\emptyset$, then each vertex of $S_{2}$ reaches two of the four
vertices among $\\{v_{1},v_{2},v_{3},v_{4}\\}$ directly and two of them via
vertices of $S_{1}$. This is implied by Claim 1 and the following: any vertex
in $S_{2}$ cannot reach the two non-adjacent vertices in
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ via a vertex in $S_{2}$ (as $m_{2}=0$). Hence,
contract all edges between $S_{1}$ and $\\{v_{1},v_{2},v_{3},v_{4}\\}$ to
obtain a $K_{4,4}$, a contradiction. ∎

######  Claim 4.

If $S_{4}\cup S_{3}=\\{u_{1},u_{2}\\}$ and $v_{i}$ is a common neighbor of
$u_{1}$ and $u_{2}$ for some $i\in\\{1,2,3,4\\}$, then no vertex $w\in S_{1}$
is adjacent to $v_{i}$.

###### Proof.

By Claim 3, we know that $S_{2}=\emptyset$. Therefore, each vertex in
$S_{4}\cup S_{3}$ would reach non-adjacent vertices in
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ via some vertices in $S_{1}$. If there exists
a vertex $w\in S_{1}\cap N(v_{i})$, where $v_{i}$ is as defined in the lemma
statement, then $w$ cannot be adjacent to any of $\\{u_{1},u_{2}\\}$ (else a
triangle is induced). Since $S_{2}=\emptyset$ (by Claim 3), the vertex $w$
reaches vertices in $\\{v_{1},v_{2},v_{3},v_{4}\\}\setminus\\{v_{i}\\}$ via
vertices in $S_{1}$. Contract all the edges between $S_{1}$ and
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ except $wv_{i}$ to obtain a $K_{4,4}$, a
contradiction. ∎

######  Claim 5.

If $|S_{4}|+|S_{3}|=2$, then $X=\emptyset$.

###### Proof.

Assume that $S_{4}\cup S_{3}=\\{u_{1},u_{2}\\}$ and there exists an $x\in X$.

If $|S_{4}|=2$, then $x$ reaches $u_{1}$ and $u_{2}$ directly or via some
other vertices not adjacent to $\\{v_{1},v_{2},v_{3},v_{4}\\}$ (else a
triangle is induced). Contract the edges between $x$ and those vertices (if
they exist) via which $x$ reaches $u_{1},u_{2}$ to obtain a $K_{3,5}$, a
contradiction.

If $|S_{4}|=1$ and without loss of generality $u_{1}\in S_{4}$ and $u_{2}\in
S_{3}$, then $x$ reaches $u_{1}$ directly or via some other vertex $w_{1}$ not
adjacent to $\\{v_{1},v_{2},v_{3},v_{4}\\}$ (else a triangle is induced).
Contract the edge $xw_{1}$ if it exists. Observe that $u_{2}$ is adjacent to
some vertex $w_{2}\in S_{1}$ in order to reach all of
$\\{v_{1},v_{2},v_{3},v_{4}\\}$. Contract $u_{2}w_{2}$. Note that $x$ reaches
$u_{2}$ directly, or via $w_{2}$ or via some other vertex $w_{3}$ which is not
adjacent to $\\{v_{1},v_{2},v_{3},v_{4}\\}$. Contract $xw_{3}$, if it exists,
to obtain a $K_{3,5}$, a contradiction.

If $|S_{4}|=0$ and thus $u_{1},u_{2}\in S_{3}$, then $u_{1}$ and $u_{2}$ may
be non-adjacent to the same or different vertices in
$\\{v_{1},v_{2},v_{3},v_{4}\\}$.

  * Case 1.

If they are non-adjacent to different vertices of
$\\{v_{1},v_{2},v_{3},v_{4}\\}$, then without loss of generality assume that
$u_{i}$ is not adjacent to $v_{i}$ for $i\in\\{1,2\\}$. In this case, $u_{i}$
must reach $v_{i}$ via some $w_{i}\in S_{1}$ (by Claim 1) and $x$ must reach
$u_{i}$ directly or via $w_{i}$ or via some $w^{\prime}_{i}\in S_{1}$ with
$w^{\prime}_{i}\not\in\\{w_{1},w_{2}\\}$. Contract the edges $u_{i}w_{i}$ and
$xw^{\prime}_{i}$ (if they exist) for all $i\in\\{1,2\\}$ to obtain a
$K_{3,5}$, a contradiction.

  * Case 2.

If they are non-adjacent to the same vertex, without loss of generality say,
$v_{4}$ of $\\{v_{1},v_{2},v_{3},v_{4}\\}$, then $v_{4}$ must have at least
two neighbors $w_{1},w_{2}$ as the degree of $v_{4}$ is at least three. Also
$w_{1},w_{2}\in S_{1}$ (by Claim 1). Due to Claims 3 and 4, we know that the
only way for $w_{i}$ to reach $v_{1}$ is via $u_{1}$ or $u_{2}$. Moreover, for
each $i\in\\{1,2\\}$, $u_{i}$ must reach $v_{4}$ via some vertex of $S_{1}$
(by Claim 1). Therefore, we must have a perfect matching between
$\\{u_{1},u_{2}\\}$ and $\\{w_{1},w_{2}\\}$. Without loss of generality,
assume that perfect matching be $\\{u_{1}w_{1},u_{2}w_{2}\\}$. Furthermore,
observe that if $x$ is adjacent to any one of $u_{1}$ or $u_{2}$, we can
rename the vertices of $N(v)$ to reduce this to a case where $|S_{4}|\geq 1$,
which we have already handled earlier in the proof of this lemma. Therefore,
$x$ must reach $u_{i}$ via $w_{i}$ or via some vertex
$w^{\prime}_{i}\not\in\\{u_{1},u_{2},w_{1},w_{2}\\}$ for all $i\in\\{1,2\\}$.
Contract the edges $u_{i}w_{i}$ and $xw^{\prime}_{i}$ (if they exist) for all
$i\in\\{1,2\\}$ to obtain a $K_{3,5}$, a contradiction.

This concludes the proof. ∎

Now that we have shown the set $X=\emptyset$ when $|S_{4}|+|S_{3}|=2$, we can
try to characterize the graphs for this case.

######  Lemma 5.

If $\delta(G)=3$ and $d(v)=\Delta(G)\geq 4$ for a graph
$G\in\mathcal{PP}_{2}$, then the following holds: if $|S_{4}|=2$, then $G$ is
isomorphic to $K_{3,4}$.

###### Proof.

If $|S_{4}|=2$, then $X=S_{3}=S_{2}=S_{1}=\emptyset$ due to Claims 2, 3, 4 and
5. The only vertices in the graphs other than
$\\{v,v_{1},v_{2},v_{3},v_{4}\\}$ are the two vertices in $S_{4}$. Thus $G$ is
isomorphic to $K_{3,4}$. ∎

######  Claim 6.

It is not possible to have $|S_{4}|=|S_{3}|=1$.

###### Proof.

If $|S_{4}|=|S_{3}|=1$, then without loss of generality assume that $u_{1}\in
S_{4}$, $u_{2}$ $\in S_{3}\setminus N(v_{4})$. Observe that
$X=S_{3}=S_{2}=\emptyset$ due to Claims 2, 3 and 5. Moreover, all the vertices
in $S_{1}$ are adjacent to $v_{4}$ due to Claim 4. As $u_{2}$ must reach
$v_{4}$ via some vertex of $S_{1}$, the set $S_{1}$ is not empty. However, any
vertex of $S_{1}$ has exactly two neighbors, namely $v_{4}$ and $u_{2}$,
contradicting $\delta(G)=3$. ∎

######  Lemma 6.

If $\delta(G)=3$ and $d(v)=\Delta(G)\geq 4$ for a graph
$G\in\mathcal{PP}_{2}$, then the following holds: if $|S_{3}|=2$, then $G$ is
isomorphic to $W^{+}_{8}$.

###### Proof.

Assume that $S_{3}=\\{u_{1},u_{2}\\}$. Thus $X=S_{4}=S_{2}=\emptyset$ due to
Claims 5, 2 and 3. Observe that it is enough to consider the following two
cases: (i) $u_{1}$ and $u_{2}$ are both non-adjacent to $v_{4}$, and (ii)
$u_{i}$ is non-adjacent to $v_{i}$ for $i\in\\{1,2\\}$.

  * Case (i).

If $u_{1}$ and $u_{2}$ are both non-adjacent to $v_{4}$, then all the vertices
in $S_{1}$ are adjacent to $v_{4}$ due to Claim 4. The vertices
$v,v_{1},v_{2},v_{3},v_{4},u_{1},$ and $u_{2}$ and the vertices belonging to
$S_{1}$ are all of the vertices of $G$. As $\delta(G)=3$, each vertex of
$S_{1}$ must be adjacent to both $u_{1}$ and $u_{2}$. Furthermore, $S_{1}$
must have at least two vertices, say $w_{1}$ and $w_{2}$, as $\delta(G)=3$.
Now contract $vv_{4}$ to obtain a $K_{3,5}$ induced by
$\\{u_{1},u_{2},(vv_{4})\\}\sqcup\\{v_{1},v_{2},v_{3},w_{1},w_{2}\\}$ where
$(vv_{4})$ denotes the new vertex obtained by contracting the edge $vv_{4}$.
Thus this case is not possible since $K_{3,5}$ is not projective planar.

  * Case (ii).

If $u_{i}$ is non-adjacent to $v_{i}$ for $i\in\\{1,2\\}$, then all the
vertices in $S_{1}$ are adjacent to either $v_{1}$ or $v_{2}$ due to Claim 4.
Therefore, the vertices $v,v_{1},v_{2},v_{3},v_{4},u_{1},$ and $u_{2}$ and the
vertices belonging to $S_{1}$ are all of the vertices of $G$. Suppose that
$S_{1}=\\{w_{1},w_{2},\ldots,w_{k},w^{\prime}_{1},w^{\prime}_{2},\ldots,w^{\prime}_{r}\\}$
where $w_{i}$s are adjacent to $v_{1}$ and $w^{\prime}_{j}$s are adjacent to
$v_{2}$ where $(i,j)\in\\{1,2,\ldots,k\\}\times\\{1,2,\ldots,r\\}$. Each
$w_{i}$ reaches $v_{3}$ via $u_{1}$ and each $w^{\prime}_{j}$ is reaches
$v_{3}$ via $u_{2}$ for all
$(i,j)\in\\{1,2,\ldots,k\\}\times\\{1,2,\ldots,r\\}$. Furthermore as
$\delta(G)=3$, each $w_{i}$ must be adjacent to some $w^{\prime}_{j}$ and each
$w^{\prime}_{p}$ must be adjacent to some $w_{q}$. Without loss of generality
and due to symmetry, we may assume that $1\leq r\leq k$. If $k\geq 2$, then
contract the edges $u_{2}w^{\prime}_{j}$ for all $j\in\\{1,2,\ldots,r\\}$ to
obtain the new vertex $(u_{2}w^{\prime}_{j})$, and contract the edge $vv_{1}$
to obtain the new vertex $(vv_{1})$. Observe that, in this contracted graph,
the vertices
$\\{u_{1},(vv_{1}),(u_{2}w^{\prime}_{j})\\}\sqcup\\{w_{1},w_{2},v_{2},v_{3},v_{4}\\}$
induce a $K_{3,5}$ subgraph, a contradiction. Therefore, $k=r=1$. Thus $G$ is
isomorphic to $W_{8}^{+}$.

This ends the proof of the lemma. ∎

This concludes the case when we have $|S_{4}|+|S_{3}|=2$. We will present the
summary of it in the following lemma.

######  Lemma 7.

If $\delta(G)=3$ and $d(v)=\Delta(G)\geq 4$ for a graph
$G\in\mathcal{PP}_{2}$, then the following holds: if ${|S_{4}|+|S_{3}|=2}$,
then $G$ is isomorphic to $K_{3,4}$ or $W_{8}^{+}$.

###### Proof.

Follows directly from Lemma 5, Claim 6, and Lemma 6. ∎

It remains to analyse the situations when $|S_{4}|+|S_{3}|\leq 1$. The first
case is when $|S_{4}|+|S_{3}|=1$.

####  2.3.4 Case: $|S_{4}|+|S_{3}|=1$

######  Claim 7.

If $|S_{4}|+|S_{3}|=1$, then $S_{2}\neq\emptyset$.

###### Proof.

Let us assume the contrary and suppose that $S_{2}=\emptyset$. Furthermore,
assume that $S_{4}\cup S_{3}=\\{u_{1}\\}$ and that $u_{1}$ is adjacent to
$\\{v_{1},v_{2},v_{3}\\}$. First we will show that it is not possible for any
$v_{i}$, for $i\in\\{1,2,3\\}$, to have two neighbors in $S_{1}$.

Hence without loss of generality assume that $v_{1}$ is adjacent to
$w_{1},w_{2}\in S_{1}$. Observe that both $w_{1}$ and $w_{2}$ must reach
$v_{2},v_{3},$ and $v_{4}$ via some vertices from
$S_{1}\setminus\\{w_{1},w_{2}\\}$ and $u_{1}$ must reach $v_{4}$ via some
vertex from $S_{1}\setminus\\{w_{1},w_{2}\\}$ (all due to Claim 1). Now
contract all the edges between $\\{v_{2},v_{3},v_{4}\\}$ and
$S_{1}\setminus\\{w_{1},w_{2}\\}$ to obtain a $K_{4,4}$-minor, a
contradiction. Thus each $v_{i}$s, for $i\in\\{1,2,3\\}$, can have at most one
neighbor in $S_{1}$.

However, $\delta(G)=3$ implies that each $v_{i}$ must be adjacent to exactly
one vertex (say) $w_{i}$ from $S_{1}$ for $i\in\\{1,2,3\\}$. Now note that
$w_{1}$ must reach $v_{2}$ and $v_{3}$ via $w_{2}$ and $w_{3}$, respectively
and $w_{2}$ must reach $v_{3}$ via $w_{3}$. This creates a triangle induced by
$\\{w_{1},w_{2},w_{3}\\}$ in $G$, a contradiction. ∎

######  Claim 8.

If $|S_{4}|=1$ and $|S_{3}|=0$, then $X=\emptyset$.

###### Proof.

Let $S_{4}=\\{u_{1}\\}$ and let $x\in X$. Claim 7 implies the existence of a
vertex $w_{1}\in S_{2}$. Without loss of generality assume that $w_{1}$ is
adjacent to $v_{1}$ and $v_{2}$.

Note that $x$ reaches $u_{1}$ directly or via some vertex $a$ (say) not
adjacent to any of $\\{v_{1},v_{2},v_{3},v_{4}\\}$ in order to avoid creating
a triangle in $G$. Moreover, $w_{1}$ reaches $x,v_{3},$ and $v_{4}$ via some
vertices not adjacent to any of $\\{v_{1},v_{2}\\}$. Let $A$ denote the set of
vertices via which $w_{1}$ reaches $x,v_{3},$ and $v_{4}$. Contract the edges
between $A\setminus\\{a\\}$ and $w_{1}$ and the edge $xa$. The vertices
$\\{v,w_{1},u_{1}\\}\sqcup\\{x,v_{1},v_{2},v_{3},v_{4}\\}$ form the partition
of a $K_{3,5}$-minor, a contradiction. ∎

######  Claim 9.

If $|S_{4}|=1$ and $|S_{3}|=0$, then $m_{2}=1$.

###### Proof.

By Claim 2, $m_{2}\leq 1$. Next, suppose that $S_{4}=\\{u_{1}\\}$ and
$m_{2}=0$. That means every vertex of $S_{2}$ (which is non-empty by Claim 7)
must reach its non-adjacent $v_{i}$s via vertices of $S_{1}$ (by Claim 1 and
$m_{2}=0$). Therefore, if $|S_{2}|\geq 2$, then contracting the edges between
$S_{1}$ and $\\{v_{1},v_{2},v_{3},v_{4}\\}$ will create a $K_{4,4}$-minor.

Thus, we have $|S_{2}|=1$. Without loss of generality assume that
$S_{2}=\\{w\\}$ and that $w$ is adjacent to $v_{1}$ and $v_{2}$.

Notice that $w$ must reach $v_{3}$ and $v_{4}$ via $w_{3},w_{4}\in S_{1}$,
respectively (by Claim 1 and $m_{2}=0$). Thus to avoid creating a triangle,
$w_{3}$ must reach $v_{4}$ via $w_{4}^{\prime}\in S_{1}$. Moreover, to avoid
creating a triangle, $w_{4}^{\prime}$ must reach $v_{1}$ via some $w_{1}\in
S_{1}$.

Notice that, $w_{1}$ reaches $v_{2},v_{3},$ and $v_{4}$ via some elements of
$S_{1}$. Thus, if we contract all the edges between $S_{1}$ and
$\\{v_{2},v_{3},v_{4}\\}$, we will create a $K_{4,4}$-minor.

Therefore, $m_{2}\geq 1$. Since $m_{2}\leq 1$ by Claim 2, we have $m_{2}=1$. ∎

######  Lemma 8.

If $\delta(G)=3$ and $\Delta(G)\geq 4$ for a graph $G\in\mathcal{PP}_{2}$,
then the following holds: if $|S_{4}|=1$ and $|S_{3}|=0$, then $G$ is
isomorphic to $K_{3,4}^{*}$.

###### Proof.

Let $S_{4}=\\{u_{1}\\}$ and, thus, by Claim 9 we know that $m_{2}=1$. Then
without loss of generality we may assume the existence of an edge $w_{1}w_{2}$
such that $w_{1},w_{2}\in S_{2}$, $w_{1}$ is adjacent to $v_{1}$ and $v_{2}$,
and $w_{2}$ is adjacent to $v_{3}$ and $v_{4}$. If there are no other vertex
or edge in $G$, then $G$ is isomorphic to $K_{3,4}^{*}$.

However, if there is another vertex $w_{3}\in S_{2}$ and if $w_{3}$ reaches
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ directly or via some vertices except $w_{1}$
and $w_{2}$, then contract the edge $w_{1}w_{2}$. Also contract the edges
between $w_{3}$ and the vertices via which $w_{3}$ reaches $v_{i}$s, for
$i\in\\{1,2,3,4\\}$. This will result in a $K_{4,4}$-minor.

On the other hand, if there is a $w_{3}\in S_{2}$ and if $w_{3}$ reaches
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ directly or via $w_{i}$ for some
$i\in\\{1,2\\}$, then $G$ is the graph $F_{1}$ (depicted in Fig. 2(b)) that
contains the graph $F_{0}$ (depicted in Fig. 2(a)) as a subgraph, and thus as
a minor. ∎

So far we were dealing with the case when $G$ is a graph with $|S_{4}|=1$ and
$|S_{3}|=0$. Now we turn our attention towards the case when $G$ is a graph
with $|S_{4}|=0$ and $|S_{3}|=1$. Initially, we will observe some properties
that this condition implies. However, finally, the satisfaction of those
properties will turn out to be impossible, thereby proving that there are no
required graphs with $|S_{4}|=0$ and $|S_{3}|=1$.

######  Claim 10.

If $|S_{4}|=0$ and $|S_{3}|=1$, then $X=\emptyset$.

###### Proof.

Suppose that $X\neq\emptyset$ and $x\in X$. Let $S_{3}=\\{u_{1}\\}$ and
without loss of generality let $u_{1}$ be adjacent to $v_{1},v_{2},v_{3}$.
Therefore, $u_{1}$ must reach $v_{4}$ via $w_{4}\in S_{1}$ (by Claim 1). We
know that $S_{2}\neq\emptyset$ due to Claim 7. Also let $u_{2}\in S_{2}$.

If $u_{2}$ reaches $v_{4}$ directly or via any vertex other than $w_{4}$, then
contract the edge $u_{1}w_{4}$, all the edges connecting $u_{2}$ to its
neighbors via which $u_{2}$ reaches $v_{1},v_{2},v_{3}$ or $v_{4}$, and all
the edges connecting $x$ to its neighbors via which $x$ reaches $u_{1}$ and
$u_{2}$, in order to obtain a $K_{3,5}$-minor (see the vertices in the
partition $\\{v,u_{1},u_{2}\\}\sqcup\\{x,v_{1},v_{2},v_{3},v_{4}\\}$).

Thus $u_{2}$ reaches $v_{4}$ via $w_{4}$ and nothing else. Hence without loss
of generality, we may assume that $u_{2}$ is adjacent to $v_{1}$ and $v_{2}$
and that $u_{2}$ reaches $v_{3}$ via $w_{3}\in S_{1}$ (if $w_{3}\in S_{2}$,
then $w_{3}$ must be adjacent to $v_{3},v_{4}$ and by similar arguments as the
previous case existence $K_{3,5}$ minor can be shown). Moreover, as
$\delta(G)=3$, there must be a $w^{\prime}_{4}\in S_{1}$ adjacent to $v_{4}$.
On the other hand, $v_{1}$ cannot have a neighbor in $S_{1}$, as otherwise we
may contract all the edges between $S_{1}$ and $\\{v_{2},v_{3},v_{4}\\}$ to
obtain a $K_{4,4}$-minor. Therefore, $w^{\prime}_{4}$ must reach $v_{1}$ via
$u_{1}$ (if $w^{\prime}_{4}$ reaches $v_{1}$ via $u_{2}$, then a
$K_{3,5}$-minor is formed: see the vertices in the partition
$\\{v,u_{1},u_{2}\\}\sqcup\\{x,v_{1},v_{2},v_{3},v_{4}\\}$). Now contract the
edges $u_{1}w^{\prime}_{4},u_{2}w_{3},u_{2}w_{4}$, and all the edges
connecting $x$ to its neighbors via which $x$ reaches $u_{1},u_{2}$. If $x$ is
adjacent to $w_{4}$, then also contract the edge connecting $x$ to its
neighbor via which $x$ reaches $w^{\prime}_{4}$. This creates a
$K_{3,5}$-minor (see the vertices in the partition
$\\{v,u_{1},u_{2}\\}\sqcup\\{x,v_{1},v_{2},v_{3},v_{4}\\}$). ∎

######  Claim 11.

If $|S_{4}|=0$ and $|S_{3}|=1$, then $m_{2}=1$.

###### Proof.

We already know that $m_{2}=0$ or $1$ due to Claim 2.

If $m_{2}=0$, then $|S_{2}|\leq 1$ as otherwise we can contract all the edges
between $S_{1}$ and $\\{v_{1},v_{2},v_{3},v_{4}\\}$ to obtain a
$K_{4,4}$-minor. Thus $|S_{2}|=1$ due to Lemma 7. Without loss of generality
assume that $S_{3}=\\{u_{1}\\}$, $S_{2}=\\{u_{2}\\}$, $u_{1}$ is adjacent to
$v_{1},v_{2},v_{3}$ and $u_{2}$ is adjacent to $v_{1}$. If $v_{1}$ is adjacent
to some vertex of $S_{1}$, then we can contract all the edges between $S_{1}$
and $\\{v_{2},v_{3},v_{4}\\}$ and obtain a $K_{4,4}$-minor. Thus $v_{1}$
cannot have a neighbor in $S_{1}$. Hence every vertex of $S_{1}$ must reach
$v_{1}$ via $u_{1}$ or $u_{2}$.

If $u_{2}$ is adjacent to $v_{4}$ as well, then $u_{2}$ must reach $v_{2}$,
$v_{3}$ via some $w_{2},w_{3}\in S_{1}$, respectively. Now $w_{2}$ must reach
$v_{3}$ via some vertex $w^{\prime}_{3}\in S_{1}$. Observe that it is not
possible to have $w_{3}=w^{\prime}_{3}$ as $G$ is triangle-free. Now
$w^{\prime}_{3}$ must reach $v_{1}$ via $u_{1}$ or $u_{2}$. In any case, this
will create a triangle. Therefore, $u_{2}$ is not adjacent to $v_{4}$. Thus we
may assume without loss of generality that $u_{2}$ is adjacent to $v_{2}$.

If $u_{2}$ is adjacent to $v_{2}$, then $u_{2}$ must reach $v_{3}$ via some
$w_{3}\in S_{1}$ and $w_{3}$ must reach $v_{4}$ via some $w_{4}\in S_{1}$.
Observe that $u_{2}$ cannot be adjacent to $w_{4}$ in order to avoid creating
a triangle. Therefore, $u_{2}$ must reach $v_{4}$ via some $w^{\prime}_{4}\in
S_{1}$. Note that $w^{\prime}_{4}$ must reach $v_{3}$ via some distinct
$w^{\prime}_{3}\in S_{1}$ in order to avoid creating triangle.

By what we have already noted above in this proof, we know that the only way
for $w^{\prime}_{3}$ to reach $v_{1}$ is via $u_{1}$ or $u_{2}$. In each case
a triangle will be created. ∎

######  Claim 12.

If $|S_{4}|=0$, then it is not possible to have $|S_{3}|=1$.

###### Proof.

Suppose the contrary. We already know that $m_{2}=1$ due to Claim 11. Thus
note that without loss of generality we may assume that $S_{3}=\\{u_{1}\\}$,
$u_{2},u_{3}\in S_{2}$, $u_{2}u_{3}\in E(G)$, $u_{1}$ is adjacent to
$\\{v_{1},v_{2},v_{3}\\}$, $u_{2}$ is adjacent to $\\{v_{1},v_{2}\\}$, $u_{3}$
is adjacent to $\\{v_{3},v_{4}\\}$ and $u_{1}$ reaches $v_{4}$ via $w_{1}\in
S_{1}$.

Observe that any vertex in $S_{2}\setminus\\{u_{2},u_{3}\\}$ will force a
$K_{4,4}$-minor or a $F_{2}$ (depicted in Fig. 2(c) which contains $F_{0}$,
depicted in Fig. 2(a), as a minor) as a subgraph of $G$ (this is similar to
the second half of the proof of Lemma 8). Thus we may infer that
$S_{2}=\\{u_{2},u_{3}\\}$. Note that, according to the partial description of
$G$ till now $w_{1}$ has two neighbors. Due to the minimum degree requirement,
it must have another neighbor. If $u_{2}$ is a neighbor of $w_{1}$, then note
that $v_{1},v_{2},v_{3}$, and $w_{1}$ are neighbors of $u_{1}$ such that $v$
is adjacent to three of them and $u_{2}$ is adjacent to three of them. This
reduces the case to where $|S_{3}|=2$, which is already taken care of.

Therefore, $w_{1}$ is adjacent to another vertex $w_{2}\in S_{1}$. Note that,
if $w_{2}$ reaches $v_{1},v_{2},v_{3},$ and $v_{4}$ directly or via vertices
from $S_{1}$, then contracting the edge $u_{2}u_{3}$ and all the edges between
$S_{1}$ and $\\{v_{1},v_{2},v_{3},v_{4}\\}$ except for the edge having $w_{2}$
as an endpoint creates a $K_{4,4}$-minor. If $w_{2}$ is adjacent to either of
$v_{1}$ or $v_{2}$ (without loss of generality assume it is adjacent to
$v_{1}$), then it reaches $v_{2}$ and $v_{3}$ via vertices of $A\subseteq
S_{1}$. Now contracting edges $w_{1}v_{4}$, $u_{2}u_{3}$ and edges between
$w_{2}$ and $A$, we get a $K_{4,4}$-minor. Thus, the following situation is
forced: $w_{2}$ is adjacent to $v_{3}$ and $u_{2}$. This creates the subgraph
$F_{2}$ (depicted in Fig. 2(c)) in $G$ which contains $F_{0}$ (depicted in
Fig. 2(a)) as a minor, a contradiction. ∎

This concludes the case when we have $|S_{4}|+|S_{3}|=1$. We will present the
summary of it in the following lemma.

######  Lemma 9.

If $\delta(G)=3$ and $d(v)=\Delta(G)\geq 4$ for a graph
$G\in\mathcal{PP}_{2}$, then the following holds: if ${|S_{4}|+|S_{3}|=1}$,
then $G$ is isomorphic to $K_{3,4}^{*}$ or $W_{8}^{+}$.

###### Proof.

Follows directly from Lemma 8 and Claim 12. ∎

This brings us to the case where $|S_{4}|+|S_{3}|=0$.

####  2.3.5 Case: $|S_{4}|+|S_{3}|=0$

######  Claim 13.

It is not possible to have $|S_{4}|=|S_{3}|=|S_{2}|=0$.

###### Proof.

As $\delta(G)\geq 3$, each $v_{i}$ must have at least two neighbors in
$S_{1}$. Thus without loss of generality assume that $v_{i}$ is adjacent to
$w_{i},w^{\prime}_{i}\in S_{1}$ for all $i\in\\{1,2,3,4\\}$. Moreover, without
loss of generality, we may suppose that $w_{1}$ reaches $v_{i}$ via $w_{i}$
for all $i\in\\{2,3,4\\}$. Note that as $G$ is triangle-free,
$\\{w_{2},w_{3},w_{4}\\}$ is an independent set. Therefore, contracting the
edges between the vertices of $\\{v_{1},v_{2},v_{3},v_{4}\\}$ and the vertices
of $(S_{1}\setminus\\{w_{2},w_{3},w_{4}\\})$ creates a $K_{4,4}$-minor. ∎

Now we will consider the case when $|S_{2}|\geq 1$.

######  Claim 14.

If $|S_{4}|=|S_{3}|=0$, then it is not possible for $v_{i}$, for all
$i\in\\{1,2,3,4\\}$, to have three or more neighbors in $S_{2}$.

###### Proof.

Let us assume the contrary. Without loss of generality suppose that $v_{1}$ is
adjacent to $u_{1},u_{2},u_{3}\in S_{2}$. Furthermore suppose that $u_{1}$ is
adjacent to $v_{2}$ as well. Observe that $\\{u_{1},u_{2},u_{3}\\}$ is an
independent set as $G$ is triangle-free.

If $u_{2}$ or $u_{3}$ is also adjacent to $v_{2}$, then by renaming $v_{1}$ as
$v$, the case reduces to $|S_{3}|+|S_{4}|\geq 1$ which has been handled
before.

Thus without loss of generality, we may assume that $u_{2}$ is adjacent to
$v_{3}$ and $u_{3}$ is adjacent to $v_{4}$. Then $u_{1}$ must reach $v_{3}$
and $v_{4}$; $u_{2}$ must reach $v_{2}$ and $v_{4}$; and $u_{3}$ must reach
$v_{2}$ and $v_{3}$, via some vertices of $S_{1}\cup S_{2}$. If they use
vertices from $S_{2}$, then those vertices must be distinct. Let $A$ be the
vertices via which $u_{1},u_{2},$ and $u_{3}$ reach $v_{2},v_{3},$ and
$v_{4}$. Contract the edges between $A\cap S_{2}$ and
$\\{u_{1},u_{2},u_{3}\\}$. Also, contract the edges between $A\cap S_{1}$ and
$\\{v_{2},v_{3},v_{4}\\}$. We will obtain a $K_{4,4}$-minor, a contradiction.

Thus we have considered all the cases up to symmetry and have proved the
claim. ∎

######  Claim 15.

If $|S_{4}|=|S_{3}|=0$ , then it is not possible to have $u_{1},u_{2}\in
S_{2}$ having
$N(u_{1})\cap\\{v_{1},v_{2},v_{3},v_{4}\\}=N(u_{2})\cap\\{v_{1},v_{2},v_{3},v_{4}\\}$.

###### Proof.

Let us assume the contrary. Without loss of generality suppose that $u_{1}$
and $u_{2}$ are adjacent to both $v_{1}$ and $v_{2}$.

Note that it is not possible to have any vertex other than $v,u_{1}$, and
$u_{2}$ adjacent to $v_{1}$ (or $v_{2}$) as otherwise our case will get
reduced to the case where $|S_{3}|+|S_{4}|\geq 1$ by renaming $v_{1}$ as $v$
which we have already taken care of.

Therefore, every vertex from $V(G)\setminus(N[v]\cup\\{u_{1},u_{2}\\})=A$
(say) is adjacent to either $u_{1}$ or $u_{2}$ in order to reach $v_{1}$ and
$v_{2}$. Since $\delta(G)\geq 3$, $v_{3}$ has two more neighbors. Both these
neighbors are adjacent to $u_{1}$ or $u_{2}$. If any vertex from $A$ is
adjacent to both $u_{1}$ and $u_{2}$, then one of $u_{1}$ or $u_{2}$, without
loss of generality assumes $u_{1}$, has degree 4. Then our case will get
reduced to the case where $|S_{3}|+|S_{4}|\geq 1$ by renaming $u_{1}$ as $v$
which we have already taken care of.

As diameter of $G$ is $2$, $u_{1},u_{2}$ must reach
$N(v)\setminus\\{v_{1},v_{2}\\}$ via some vertices from $A$. Let $A_{i}$ be
the set of vertices from $A$ via which $u_{i}$ reaches the vertices of
$N(v)\setminus\\{v_{1},v_{2}\\}$ where $i\in\\{1,2\\}$. Due to the observation
made in the previous paragraph, we know that the sets $A_{1}$ and $A_{2}$ are
disjoint.

If $X\neq\emptyset$, then contract the edges between $A_{i}$ and $\\{u_{i}\\}$
for each $i\in\\{1,2\\}$ to obtain a $K_{3,5}$-minor, a contradiction (see the
vertices in the partition
$\\{v,u_{1},u_{2}\\}\sqcup\\{x,v_{1},v_{2},v_{3},v_{4}\\}$, where $x\in X$).
Thus we may assume that $X=\emptyset$.

If there exists $u_{3}\in S_{2}$, it must be adjacent to both $u_{1}$ and
$u_{2}$ in order to reach them. This follows from Claim 14. But we have
already shown that this is not possible. Thus there are no vertices in $S_{2}$
other than $u_{1}$ and $u_{2}$.

However as $\delta(G)\geq 3$, there are at least two neighbors
$w_{i1},w_{i2}\in S_{1}$ of $v_{i}$ for $i\in\\{3,4\\}$. Without loss of
generality suppose that $w_{31}$ reaches $v_{1}$ and $v_{2}$ via $u_{1}$.
Therefore, $w_{31}$ have to reach $v_{4}$ via a vertex of $S_{1}\cap
N(v_{4})$, say $w_{41}$. Now as $G$ is triangle free, $w_{41}$ reaches $v_{1}$
and $v_{2}$ via $u_{2}$. If $w_{32}$ is adjacent to $w_{41}$, then a triangle
is induced as $w_{32}$ has to be adjacent to $u_{1}$ or $u_{2}$ in order to
reach $v_{1}$ and $v_{2}$. Thus $w_{32}$ is not adjacent to $w_{41}$. Next,
observe that $w_{32}$ must reach $w_{41}$ via $u_{2}$. Finally, $w_{32}$ must
reach $v_{4}$ via some vertex in $S_{1}\cap N(v_{4})$, say $w_{42}$ and, then
$w_{42}$ must reach $v_{1}$ and $v_{2}$ via $u_{1}$.

This so-obtained graph is isomorphic to the graph $F_{3}$ depicted in Fig. 1.
∎

######  Claim 16.

If $|S_{4}|=|S_{3}|=0$, then it is not possible to have three vertices of
$S_{2}$ non-adjacent to $v_{i}$, for all $i\in\\{1,2,3,4\\}$.

###### Proof.

Assume the contrary and let $u_{1},u_{2},u_{3}\in S_{2}$ be non-adjacent to
$v_{4}$. Contract all edges between $S_{2}\setminus\\{u_{1},u_{2},u_{3}\\}$
and $\\{u_{1},u_{2},u_{3}\\}$. Also, contract the edges between $S_{1}$ and
$\\{v_{1},v_{2},v_{3},v_{4}\\}$. This will create a $K_{4,4}$-minor, a
contradiction. ∎

######  Claim 17.

If $|S_{4}|=|S_{3}|=0$, then $|S_{2}|\leq 4$.

###### Proof.

Follows directly from Claims 14, 15 and 16. ∎

######  Lemma 10.

If $\delta(G)=3$ and $\Delta(G)\geq 4$ for a graph $G\in\mathcal{PP}_{2}$,
then the following holds: if ${|S_{4}|=|S_{3}|=0}$ and $|S_{2}|=4$, then $G$
is isomorphic to $M^{=}_{11},M^{-}_{11}$, or $M_{11}$.

###### Proof.

Assume that $S_{2}=\\{u_{1},u_{2},u_{3},u_{4}\\}$. Thus due to Claims 14, 15
and 16 without loss of we may suppose that $u_{i}$ is adjacent to $v_{i}$ and
$v_{i+1}$, for all $i\in\\{1,2,3,4\\}$ and the $+$ operation on the indices is
taken modulo $4$. If $S_{2}$ does not have a perfect matching, then it will
force a $K_{4,4}$-minor. Thus we must have the edges $u_{1}u_{3}$ and
$u_{2}u_{4}$. Also $X=\emptyset$, as otherwise there will be a $K_{3,5}$-minor
in $G$ (see the partition
$\\{v,(u_{1}u_{3}),(u_{2}u_{4})\\}\sqcup\\{x,v_{1},v_{2},v_{3},v_{4}\\}$,
where $x\in X$).

Next, we claim that for all $i\in\\{1,2,3,4\\}$, $|N(v_{i})\cap S_{1}|\leq 1$.
Suppose $|N(v_{1})\cap S_{1}|\geq 2$. Let $w_{1},w_{2}\in N(v_{1})\cap S_{1}$.
Then $w_{1}$ reaches $v_{2}$ either via $u_{2}$ or some vertex in
$N(v_{2})\cap S_{1}$, and $w_{1}$ reaches $v_{4}$ either via $u_{3}$ or some
vertex in $N(v_{4})\cap S_{1}$. Similarly $w_{2}$ reaches $v_{2}$ and $v_{4}$.
Contract the edge $v_{2}u_{2}$ and $v_{4}u_{3}$ and the edges between $S_{1}$
and $\\{v_{2},v_{4}\\}$ to obtain a $K_{3,5}$-minor, a contradiction (see the
partition
$\\{v_{1},(v_{2}u_{2}),(v_{4}u_{3})\\}\sqcup\\{w_{1},w_{2},u_{1},u_{4},v\\}$).
Thus $|N(v_{1})\cap S_{1}|\leq 1$. A similar analysis holds for $v_{2},v_{3}$,
and $v_{4}$. Hence, for all $i\in\\{1,2,3,4\\}$, $|N(v_{i})\cap S_{1}|\leq 1$.

Next, we claim that $|S_{1}|\leq 2$. If $|S_{1}|\geq 3$, then without loss of
generality assume that $w_{1}\in N(v_{1})\cap S_{1}$. If $w_{1}$ does not
reach $\\{v_{2},v_{3},v_{4}\\}$ via $u_{2},u_{3}$, then it uses vertices from
$S_{1}$, forcing a $K_{4,4}$-minor in $G$. Thus $w_{1}$ has to use at least
one of $u_{2},u_{3}$ to reach $\\{v_{2},v_{3},v_{4}\\}$. Suppose $w_{1}$ is
not adjacent to $u_{2}$, then it is adjacent to $u_{3}$. Then $w_{1}$ reaches
$v_{2}$ via $w_{2}\in S_{1}$. Now $w_{2}$ cannot reach $v_{3}$ via $u_{2}$ or
$u_{3}$, else a triangle is induced in $G$. Thus $w_{2}$ reaches $v_{3}$ via
$w_{3}\in S_{1}$. This forms a $K_{4,4}^{-}$-minor in $G$ (see the partition
$\\{v,(u_{1}u_{3}),(u_{2}u_{4}),(w_{1}w_{2}w_{3})\\}\sqcup\\{v_{1},v_{2},v_{3},v_{4}\\}$).
Next, suppose $w_{1}$ is not adjacent to $u_{3}$, then it is adjacent to
$u_{2}$. Then, similarly, a $K_{4,4}^{-}$-minor is obtained in $G$. Thus
$|S_{1}|\leq 2$.

Observe that if $|S_{1}|=0,1$, or $2$, then $G$ is isomorphic to
$M^{=}_{11},M^{-}_{11}$, or $M_{11}$, respectively. It is easy to observe the
cases when $|S_{1}|=0,1$. For $|S_{1}|=2$, without loss of generality we will
have two cases: when the two vertices of $S_{1}$ are adjacent to $v_{1}$ and
$v_{2}$; and when the two vertices of $S_{1}$ are adjacent to $v_{1}$ and
$v_{3}$. In the first case, we get a graph isomorphic to $M_{11}$. In the
second case, we get a $K_{4,4}$-minor in $G$. We briefly describe the second
case. Let $N(v_{1})\cap S_{1}=\\{w_{1}\\}$ and $N(v_{1})\cap
S_{3}=\\{w_{2}\\}$. Then $w_{1}$ reaches $v_{2}$ via $u_{2}$, and $v_{4}$ via
$u_{3}$. And $w_{2}$ reaches $v_{4}$ via $u_{4}$, and $v_{2}$ via $u_{1}$. All
these edges are forced, or else a triangle is induced in $G$. The only
possible way that $w_{1}$ reaches $w_{2}$, without inducing a triangle in $G$,
is directly by an edge. This forms a $K_{4,4}$-minor in $G$ (see the partition
$\\{w_{1},(vv_{3}),u_{1},u_{4})\\}\sqcup\\{w_{2},v_{1},(u_{3}v_{4}),(u_{2}v_{2})\\}$).
∎

######  Lemma 11.

If $\delta(G)=3$ and $d(v)=\Delta(G)\geq 4$ for a graph
$G\in\mathcal{PP}_{2}$, then the following holds: if ${|S_{4}|=|S_{3}|=0}$ and
$|S_{2}|=3$, then $G$ is isomorphic to $M^{=}_{11},M^{-}_{11}$, or $M_{11}$.

###### Proof.

Assume that $S_{2}=\\{u_{1},u_{2},u_{3}\\}$. Thus due to Claims 14, 15, and
16, without loss of generality, we may suppose that $u_{i}$ is adjacent to
$v_{i}$ and $v_{i+1}$, for all $i\in\\{1,2,3\\}$. If $u_{1}$ is not adjacent
to $u_{3}$, then it will force a $K_{4,4}$-minor. Thus we must have the edge
$u_{1}u_{3}$.

If $N(v_{2})\cap S_{1}\neq\emptyset$, then let $w_{1}\in N(v_{2})\cap S_{1}$.
Now $w_{1}$ reaches $v_{3}$ via $w_{2}\in S_{1}$. This forces a
$K_{4,4}$-minor (see the partition
$\\{v,(u_{1}u_{3}),u_{2},(w_{1}w_{2})\\}\sqcup\\{v_{1},v_{2},v_{3},v_{4}\\}$).
Thus $N(v_{2})\cap S_{1}=\emptyset$. Similarly, by symmetry, $N(v_{3})\cap
S_{1}=\emptyset$.

Therefore, every vertex in $S_{1}$ is adjacent to $u_{2}$ to reach $v_{2}$ and
$v_{3}$. Also, every vertex in $N(v_{1})\cap S_{1}$ is adjacent to $u_{3}$ to
reach $v_{3}$, and every vertex in $N(v_{4})\cap S_{1}$ is adjacent to $u_{1}$
to reach $v_{2}$.

Next to satisfy $\delta(G)\geq 3$, $N(v_{1})\cap S_{1}$ and $N(v_{4})\cap
S_{1}$ have at least one vertex. If $|N(v_{1})\cap S_{1}|\geq 2$, then let
$w_{1},w_{1}^{\prime}\in N(v_{1})\cap S_{1}$ and $w_{2}\in N(v_{4})\cap
S_{1}$. This forces a $K_{3,5}$-minor (see the vertices in the partition
$\\{(u_{1}u_{3}),u_{2},(v_{1}vv_{4})\\}\sqcup\\{w_{1},w_{1}^{\prime},v_{2},v_{3},w_{2}\\}$).
Thus $N(v_{1})\cap S_{1}=\\{w_{1}\\}$ and $N(v_{4})\cap S_{1}=\\{w_{2}\\}$.

Now let us consider $X$. Suppose $X\neq\emptyset$: let $x\in X$. Both $u_{1}$
and $u_{3}$ are not adjacent to $x$, else $|S_{3}|\geq 1$ which we have dealt
earlier. If $u_{1}$ and $u_{3}$ do not use $w_{2}$ and $w_{1}$, respectively,
to reach $x$, then a $K_{3,5}$-minor is forced (see the vertices in the
partition
$\\{(u_{1}u_{3}),(w_{1}u_{2}w_{2}),v\\}\sqcup\\{x,v_{1},v_{2},v_{3},v_{4}\\}$).
Hence $x$ is adjacent to $w_{1},w_{2}$.

If $|X|\geq 2$, then replacing $v$ by $w_{1}$ we have $|S_{3}|\geq 1$ which we
have dealt earlier. Hence $|X|\leq 1$.

Observe that if $|X|=0$ or $1$, then $G$ is $M^{-}_{11}$ or $M_{11}$,
respectively. ∎

######  Lemma 12.

If $\delta(G)=3$ and $d(v)=\Delta(G)\geq 4$ for a graph
$G\in\mathcal{PP}_{2}$, then the following holds: if ${|S_{4}|=|S_{3}|=0}$ and
$|S_{2}|=2$, then $G$ is isomorphic to $K_{3,4}$, $K_{3,4}^{*}$, or
$W_{8}^{+}$.

###### Proof.

Assume that $S_{2}=\\{u_{1},u_{2}\\}$. Thus due to Claims 14, 15 and 16
without loss of generality we may suppose one of the two scenarios: (i)
$u_{1}$ is adjacent to $v_{1},v_{2}$, and $u_{2}$ is adjacent to $v_{2}$ and
$v_{3}$, (ii) $u_{1}$ is adjacent to $v_{1},v_{2}$, and $u_{2}$ is adjacent to
$v_{3}$ and $v_{4}$.

Case (i): First suppose $u_{1}$ is adjacent to $v_{1},v_{2}$, and $u_{2}$ is
adjacent to $v_{2}$ and $v_{3}$. Observe that $v_{2}$ cannot be adjacent to
any vertex of $S_{1}$, as otherwise a $K_{4,4}$-minor will be created. Also
$|N(v_{4})\cap S_{1}|\geq 2$ as $\delta(G)\geq 3$. Every vertex in
$N(v_{1})\cap S_{1}$ reaches $v_{2}$ via $u_{2}$, and every vertex in
$N(v_{3})\cap S_{1}$ reaches $v_{2}$ via $u_{1}$.

Now $u_{1}$ reaches $v_{4}$ via $w_{4}\in N(v_{4})\cap S_{1}$. $w_{4}$ cannot
reach $v_{3}$ via any vertex in $N(v_{3})\cap S_{1}$, as a triangle is
induced. Thus $w_{4}$ reaches $v_{3}$ via $u_{2}$.

Now $w_{4}^{\prime}\in(N(v_{4})\cap S_{1})\setminus\\{w_{4}\\}$ reaches
$v_{2}$ via $u_{1}$ or $u_{2}$. Next, $w_{4}^{\prime}$ cannot use
$N(v_{3})\cap S_{1}$ or $N(v_{1})\cap S_{1}$ to reach the yet unreached vertex
in $\\{v_{1},v_{3}\\}$, else a triangle is induced. Thus $w_{4}^{\prime}$ is
adjacent to both $u_{1}$ and $u_{2}$. Similarly, every vertex in $N(v_{4})\cap
S_{1}$ is adjacent to $u_{1}$ and $u_{2}$.

Thus any vertex in $N(v_{1})\cap S_{1}$ cannot reach any vertex in
$N(v_{3})\cap S_{1}$ via any vertex of $N(v_{4})\cap S_{1}$. Hence every
vertex in $N(v_{1})\cap S_{1}$ is adjacent to every vertex in $N(v_{3})\cap
S_{1}$. This will reduce the case to the case of $|S_{3}|+|S_{4}|\geq 1$ where
$u_{1}$ plays the role of $v$ (note that $u_{1}$ and $u_{2}$ share at least
three common neighbors).

Case (ii): Next assume that $u_{1}$ is adjacent to $v_{1},v_{2}$, and $u_{2}$
is adjacent to $v_{3}$ and $v_{4}$. Here $u_{1}$ is adjacent to $u_{2}$, as
otherwise a $K_{4,4}$-minor will be created.

Note that $|N(v_{i})\cap S_{1}|\geq 1$ as $\delta(G)\geq 3$. All vertices of
$N(v_{1})\cap S_{1}$ and $N(v_{2})\cap S_{1}$ cannot be adjacent to $u_{2}$ as
a vertex in $N(v_{1})\cap S_{1}$ reaches $v_{2}$ via a vertex in $N(v_{2})\cap
S_{1}$. Without loss of generality assume that $w_{1}\in N(v_{1})\cap S_{1}$
is not adjacent to $u_{2}$. If $x\in X$, then a $K_{3,5}$-minor will be
created (see the partition
$\\{v,w_{1},(u_{1}u_{2})\\}\sqcup\\{x,v_{1},v_{2},v_{3},v_{4}\\}$). Hence
$X=\emptyset$.

Next, we claim that $|N(v_{i})\cap S_{1}|\leq 1$. Suppose
$w_{1},w_{1}^{\prime}\in N(v_{1})\cap S_{1}$. Both of them cannot be adjacent
to $u_{2}$, else this case reduces to $|S_{3}|+|S_{4}|\geq 1$ where $v_{1}$
plays the role of $v$ (note that $v_{1}$ and $u_{2}$ have at least three
neighbors in common). Without loss of generality assume that $w_{1}\in
N(v_{1})\cap S_{1}$ is not adjacent to $u_{2}$. Thus it reaches
$v_{2},v_{3},v_{4}$ via vertices in $S_{1}$. If $w_{1}^{\prime}$ also reaches
$v_{2},v_{3},v_{4}$ via vertices in $S_{1}$, then a $K_{4,4}$-minor will be
created (see the partition
$\\{v,w_{1},w_{1}^{\prime},(u_{1}u_{2})\\}\sqcup\\{v_{1},v_{2},v_{3},v_{4}\\}$).
If $w_{1}^{\prime}$ reaches $v_{3},v_{4}$ via $u_{2}$, then let
$w_{1}^{\prime}$ reach $v_{2}$ via $w_{2}$. Now $w_{2}$ cannot be adjacent to
$u_{2}$, else a triangle is induced. Thus $w_{2}$ reaches $v_{3},v_{4}$ via
vertices in $S_{1}$. This forces a $K_{4,4}$-minor (see the partition
$\\{v,w_{1},(w_{1}^{\prime}w_{2}),(u_{1}u_{2})\\}\sqcup\\{v_{1},v_{2},v_{3},v_{4}\\}$).
Hence $|N(v_{i})\cap S_{1}|\leq 1$; and since $|N(v_{i})\cap S_{1}|\geq 1$ as
$\delta(G)\geq 3$, we have $|N(v_{i})\cap S_{1}|=1$.

Suppose $N(v_{i})\cap S_{1}=\\{w_{i}\\}$, for all $i\in\\{1,2,3,4\\}$. Then
$w_{1}$ reaches $v_{2}$ via $w_{2}$, and $w_{3}$ reaches $v_{4}$ via $w_{4}$.
Thus $w_{1}w_{2}$ and $w_{3}w_{4}$ are edges in $G$. Moreover, due to
symmetry, without loss of generality, we may assume the edges
$w_{2}u_{2},w_{3}u_{1}$ as forced as well.

This reduces the case to Case (i) of this proof where $u_{1}$ plays the role
of $v$. ∎

######  Claim 18.

If $|S_{4}|=|S_{3}|=0$, then it is not possible to have $|S_{2}|=1$.

###### Proof.

Assume that $S_{2}=\\{u_{1}\\}$ and $u_{1}$ is adjacent to $v_{1},v_{2}$. Note
that as $|S_{2}|=1$, $u_{1}$ must reach $v_{3},v_{4}$ via (say)
$w_{31},w_{41}\in S_{1}$, respectively.

Notice that $u_{1}$ and $v_{i}$ cannot have two common neighbors from $S_{1}$,
as otherwise the case will be reduced to $|S_{2}|\geq 2$ where $u_{1}$ plays
the role of $v$.

Furthermore as $\delta(G)\geq 3$, $v_{3}$ must have another neighbor
$w_{32}\in S_{1}$. As $w_{32}$ cannot be adjacent to $u_{1}$, it must reach
$v_{1},v_{2}$ via $w_{11},w_{21}\in S_{1}$, respectively. Observe that
$w_{11}$ is not adjacent to $w_{21}$ in order to avoid creating a triangle.
Thus $w_{21}$ must reach $v_{1}$ via some $w_{12}\in S_{1}$.

Now contract all the edges between $S_{1}$ and $\\{v_{2},v_{3},v_{4}\\}$. This
will create a $K_{4,4,}$-minor, a contradiction (see the partition
$\\{v,u_{1},w_{11},w_{12}\\}\sqcup\\{v_{1},v_{2},v_{3},v_{4}\\}$). ∎

This concludes the case when we have $|S_{4}|+|S_{3}|=0$. We will present the
summary of it in the following lemma.

######  Lemma 13.

If $\delta(G)=3$ and $d(v)=\Delta(G)\geq 4$ for a graph
$G\in\mathcal{PP}_{2}$, then the following holds: if ${|S_{4}|+|S_{3}|=0}$,
then $G$ is isomorphic to $K_{3,4}$ $K_{3,4}^{*}$, $W_{8}^{+}$, $M_{11}^{=}$,
$M_{11}^{-}$, or $M_{11}$.

###### Proof.

Follows directly from Lemmas 10, 11, and 12, and Claims 13 and 18. ∎

Finally, we are ready to prove Lemma 4.

Proof of Lemma 4. The result readily follows from Lemmas 7, 9, and 13. ∎

###  2.4 Concluding the proof of Theorem 1

At last, we can conclude the proof of Theorem 2.

Proof of Theorem 2. The result readily follows from Lemmas 1, 2, 3, and 4. ∎

##  3 Direct implications

In Theorem 2, we have characterized all triangle-free projective-planar graphs
having diameter $2$. This has an immediate theoretical implication in the
theory of graph homomorphisms of colored mixed graphs, signed graphs, and
oriented graphs. We are going to discuss them here.

First let us start with colored mixed graphs which were introduced by Nešetřil
and Raspaud [8]. An $(m,n)$-colored mixed graph $G$ is a graph having $m$
different types of arcs and $n$ different types of edges. Moreover, colored
homomorphism from an $(m,n)$-colored mixed graph $G$ to another
$(m,n)$-colored mixed graph $H$ is a vertex mapping $f:V(G)\rightarrow V(H)$
such that for any arc (resp., edge) $uv$ of $G$, the induced image $f(u)f(v)$
is also an arc (resp., edge) of the same type in $H$. Observe that for
$(m,n)=(0,1),(1,0),(0,2)$, and $(0,k)$ the study of colored homomorphism of
$(m,n)$-colored mixed graphs is the same as studying homomorphisms of
undirected graphs [9], oriented graphs [10], $2$-edge-colored graphs [11], and
$k$-edge-colored graphs [12], respectively. Each of these is a well-studied
topic.

Generalizing the notion of oriented absolute cliques and oriented absolute
clique number444The same is also known as oriented cliques or ocliques and
oriented clique number or oclique number. [13], Bensmail, Duffy, and Sen [14]
introduced the notion of $(m,n)$-clique and $(m,n)$-absolute clique number. An
$(m,n)$-clique $C$ is an $(m,n)$-colored mixed graph that does not admit a
colored homomorphism to any other $(m,n)$-colored mixed graph having strictly
fewer vertices. Given a family $\mathcal{F}$ of $(m,n)$-colored mixed graphs,

$\omega_{a(m,n)}(\mathcal{F})=\max\\{|V(G)|:G\in\mathcal{F}\text{ is an
}(m,n)\text{-clique}\\}.$

A handy characterization of an $(m,n)$-clique is proved by Bensmail, Duffy,
and Sen [14].

######  Proposition 1 ([14]).

An $(m,n)$-colored mixed graph $C$ is an $(m,n)$-clique if and only if every
pair of non-adjacent vertices $u,w$ of $C$ are connected by a $2$-path $uvw$
of one of the following types:

  * (i)

$uv$ and $vw$ are edges of different colors,

  * (ii)

$uv$ and $vw$ are arcs (possibly of the same color),

  * (iii)

$vu$ and $wv$ are arcs (possibly of the same color),

  * (iv)

$uv$ and $wv$ are arcs of different colors,

  * (v)

$vu$ and $vw$ are arcs of different colors,

  * (vi)

exactly one of $uv$ and $vw$ is an edge.

A $2$-path in an $(m,n)$-graph is a special $2$-path if it is one among the
six types of path listed in Proposition 1. If a $2$-path $uvw$ is a special
$2$-path, then we say that $u$ sees $w$ via $v$ and that $u$ and $w$ disagrees
on $v$. If $uvw$ is not a special $2$-path, then we say that $u$ and $w$
agrees on $v$. Due to the above proposition, we know that any underlying graph
of an $(m,n)$-clique must have a diameter of at most $2$. Moreover, the
underlying graph of an $(m,n)$-clique is called an underlying $(m,n)$-clique.

######  Observation 3.

An underlying $(m,n)$-clique has a diameter at most $2$.

Theorem 2 and Proposition 1 directly imply the following.

######  Theorem 4.

For the family $\mathcal{PP}_{2}$ of $(m,n)$-colored mixed triangle-free
projective-planar graphs

  1. (i)

$\omega_{a(1,0)}(\mathcal{PP}_{2})=9$

  2. (ii)

$\omega_{a(0,2)}(\mathcal{PP}_{2})=8$

  3. (iii)

$\omega_{a(m,n)}(\mathcal{PP}_{2})=(2m+n)^{2}+2,\text{ for all }2m+n\geq 3$.

###### Proof.

(i) Observe that the graph $W_{8}^{+}$ is an underlying $(1,0)$-clique on $9$
vertices (see Fig. 4(a) for the relevant instance). This implies
$\omega_{a(1,0)}(\mathcal{PP}_{2})\geq 9$.

|
---|---
(a) | (b)
Figure 4: (a) A $(1,0)$-clique on $9$ vertices. (b) A $(0,2)$-clique on $8$
vertices.

Let $G^{*}$ be a triangle-free projective planar $(1,0)$-clique having at
least $9$ vertices. Thus, by Observation 3 its underlying graph, say $G$, must
belong to $\mathcal{PP}_{2}$. We are going to show that such a $G^{*}$ does
not exist. Due to Theorem 2, it is enough to restrict ourselves to checking
whether any graph listed in the theorem can be $G$ or not.

As all Plesník graphs are triangle-free planar graphs, and as it is known [15]
that the largest triangle-free planar underlying $(1,0)$-clique has six
vertices. Moreover, $K_{3,3},K_{3,4},W_{8},W_{8}^{+},M_{11}^{=}$, and
$K_{3,4}^{*}$ has less or equal to nine vertices. Furthermore, using
Proposition 1 it is possible to verify that $P_{10},M_{11}$, and $M_{11}^{-}$
are not underlying $(1,0)$-cliques. Hence, we are only left with verifying
whether it is possible to have $K_{3,4}(t)$ or $K_{3,3}(t)$ as $G$ or not,
where $t\geq 3$.

Let us suppose that $G$ is either $K_{3,4}(t)$ or $K_{3,3}(t)$ for some $t\geq
2$, and $a_{1},a_{2},\ldots,a_{t}$ are its vertices of degree two. Notice
that, all the $a_{i}$s are adjacent to exactly two vertices, say
$b_{1},b_{2}$. Note that, there are vertices $b_{1}^{\prime}$ and
$b_{2}^{\prime}$ such that $b_{j}^{\prime}$ is non-adjacent to $a_{i}$ and the
only $2$-path connecting $b_{j}^{\prime}$ to $a_{i}$ is $b_{j}$, for all
$j\in\\{1,2\\}$. Thus in $G^{*}$, all $a_{i}$s must see $b_{j}^{\prime}$ via
$b_{j}$, which implies that all $a_{i}$s must agree with each other on both
$b_{1}$ and $b_{2}$. Thus, $a_{1}$ is neither adjacent to $a_{2}$ nor there is
a special $2$ path among them. Hence $G$ cannot be an underlying
$(1,0)$-clique if it is either $K_{3,4}(t)$ or $K_{3,3}(t)$ for some $t\geq
2$.

(ii) Observe that the graph $W_{8}$ is an underlying $(0,2)$-clique on $8$
vertices (see Fig. 4(b) for the relevant instance). This implies
$\omega_{a(0,2)}(\mathcal{PP}_{2})\geq 8$. The proof of the upper bound can be
done similarly to the proof of (i).

(iii) It is known [15] that
$\omega_{a(m,n)}(\mathcal{P}^{\prime})=(2m+n)^{2}+2$, for all $2m+n\geq 3$ for
the family of triangle-free planar graphs. This implies
$\omega_{a(m,n)}(\mathcal{PP}_{2})=(2m+n)^{2}+2$, for all $2m+n\geq 3$.

For the upper bound, as $(2m+n)^{2}+2\geq 11$ for all $2m+n\geq 3$, and as
every non-planar graphs except $K_{3,4}(t)$ and $K_{3,3}(t)$ for
$t\geq(2m+n)^{2}-4$ from the graphs listed in Theorem 2 has less than or equal
to $11$ vertices, it is enough to show that $K_{3,4}(t)$ and $K_{3,3}(t)$ are
not underlying $(m,n)$-cliques for $t\geq(2m+n)^{2}-4$.

Let $G^{*}$ be an $(m,n)$-clique having at least $(2m+n)^{2}+3$ vertices such
that its underlying graph $G$ is $K_{3,4}(t)$ and $K_{3,3}(t)$ for some
$t\geq(2m+n)^{2}-4$. Let $a_{1},a_{2},\ldots,a_{t}$ be the vertices of degree
two of $G$. Notice that, all the $a_{i}$s are adjacent to exactly two
vertices, say $b_{1},b_{2}$. Note that, there are vertices $b_{1}^{\prime}$
and $b_{2}^{\prime}$ such that $b_{j}^{\prime}$ is non-adjacent to $a_{i}$ and
the only $2$-path connecting $b_{j}^{\prime}$ to $a_{i}$ is $b_{j}$, for all
$j\in\\{1,2\\}$. Thus in $G^{*}$, all $a_{i}$s must see $b_{j}^{\prime}$ via
$b_{j}$. This implies that the adjacency between $a_{i}$ and $b_{j}$ is
different from the adjacency between $b_{j}^{\prime}$ and $b_{j}$, for each
$i$ and $j$. This implies that the adjacency between $a_{i}$ and $b_{j}$ can
be one of the $(2m+n)-1$ types (each type of arc gives two adjacency options
due to directions, and each type of edge gives one adjacency option). As
$a_{i}$ also must see each other via $b_{1}$ or $b_{2}$, the number of
$a_{i}$s is bounded by

$t\leq(2m+n-1)^{2}=(2m+n)^{2}-2(2m+n)+1\leq(2m+n)^{2}-5$

for all $(2m+n)\geq 3$. However, this is a contradiction as we assumed
$t\geq(2m+n)^{2}-4$. ∎

Now we turn our focus towards variants of colored homomorphism of $(0,2)$ and
$(1,0)$-colored mixed graphs (that is, $2$-edge-colored graphs and oriented
graphs). The variants are known as homomorphisms of signed graphs [16] and
pushable homomorphisms of oriented graphs [17], respectively.

Homomorphisms of signed graphs were introduced by Naserasr, Rollová, and
Sopena [16] who also defined and characterized signed absolute clique and
signed absolute clique numbers. Naserasr, Rollová, and Sopena [16] also showed
how using the notion of homomorphism of signed graph one can capture, as well
as extend, many of the classical graph theory results and conjectures
including the Four-Color Theorem and Hadwiger’s Conjecture [18]. It motivated
a number of research works and generated a lot of interest within a short span
of time [19, 20, 21, 16, 11]. In order to avoid a long series of definitions,
we would like to define the notion using its equivalent characterization.

A signed graph $(G,\Sigma)$ is a graph with either positive or negative sign
assigned to its edges. A signed absolute clique $(C,\Lambda)$ is a signed
graph whose any two non-adjacent vertices are part of a $4$ cycle having an
odd number of negative edges. Given a family $\mathcal{F}$ of signed graphs,

$\omega_{as}(\mathcal{F})=\max\\{|V(G)|:G\in\mathcal{F}\text{ and
}(G,\Sigma)\text{ is a signed absolute clique}\\}.$

On the other hand, pushable homomorphism of oriented graphs were introduced by
Klostermeyer and MacGillivray [13] which motivated some further research works
on that topic. These include one work due to Bensmail, Nandi, and Sen [22]
that introduced and characterized the notion of pushable absolute clique of
oriented graphs. In order to avoid a long series of definitions, we would like
define the notion using its equivalent characterization.

An oriented graph $\overrightarrow{G}$ is a directed graph without any
directed cycle of length $1$ or $2$. A pushable absolute clique
$\overrightarrow{C}$ is an oriented graph whose two non-adjacent vertices are
part of a $4$ cycle having an odd number of arcs in a clockwise direction.
Given a family $\mathcal{F}$ of oriented graphs,

$\omega_{ap}(\mathcal{F})=\max\\{|V(\overrightarrow{G})|:\overrightarrow{G}\in\mathcal{F}\text{
is a pushable absolute clique}\\}.$

Thus from Theorem 2 and the two characterizations (definitions), we have the
following theorem.

######  Theorem 5.

For the families $\mathcal{PP}_{2}$ (resp. $\mathcal{PP}_{2}$) of oriented
(resp. signed) triangle-free projective-planar graphs

$\omega_{ap}(\mathcal{PP}_{2})=\omega_{as}(\mathcal{PP}_{2})=7.$

###### Proof.

Observe that there exist a signed absolute clique and a pushable absolute
clique having $K_{3,4}$ as their underlying graphs (see Fig. 5 for the
relevant instances). This implies $\omega_{as}(\mathcal{PP}_{2})\geq 7$ and
$\omega_{ap}(\mathcal{PP}_{2})\geq 7$.

|
---|---
(a) | (b)
Figure 5: (a) A pushable absolute clique on $7$ vertices. (b) A signed
absolute clique on $7$ vertices.

For the upper bound, note that if $G$ is the underlying graph of a pushable
absolute clique or a signed absolute clique, then it must have the following
property: any two non-adjacent vertices of $G$ must be connected by two
internally disjoint $2$-paths. Observe that, among the graphs listed in
Theorem 2, the only graphs that have this property are $K_{3,3}$, $K_{3,4}$,
and $K_{2,t}$ for $t\geq 2$. However, notice that a pushable absolute clique
(resp., signed absolute clique) is, in particular, a $(1,0)$-clique (resp.,
$(0,2)$-clique). Moreover, the $(1,0)$-absolute clique number (resp.,
$(0,2)$-absolute clique number) for the family of triangle-free planar graphs
is at most $6$ [15]. As $K_{2,t}$ is a triangle-free planar graph, for all
$t\geq 2$, we are done. ∎

##  4 Conclusions

In this paper, we gave a characterisation of triangle-free projective planar
graphs of diameter $2$ and proved that the domination number of this class of
graphs is at most $3$. Moreover, there are only seven triangle-free projective
planar graphs with a diameter 2 for which the equality holds. This raises a
natural question.

######  Question 3.

Given a surface $\mathbb{S}$, can you find a tight upper bound on the
domination number of triangle-free graphs with diameter $2$ that can be
embedded on $\mathbb{S}$?

Goddard and Henning [5] proved that for any integer $g\geq 0$ the number of
graphs with orientable genus $g$, diameter $2$, and domination number greater
than $2$ is finite. For the $g=0$ case, that is for planar graphs, they
reported [5] that there exists only one planar graph of diameter two and
domination number greater than two. However, the analogous problem for higher
genus surfaces is still unsolved. This motivates the following question.

######  Question 4.

Given a positive integer $g$, how many triangle-free graphs of genus $g$ and
diameter $2$ are there with a domination number greater than or equal to $3$?

We observed that the maximum order of a triangle-free projective planar graph
with diameter $2$ and domination number $3$ is $11$. This motivates the
following.

######  Question 5.

Given a positive integer $g$, what is the highest order of a triangle-free
graph of genus $g$ and diameter $2$ with a domination number greater than $3$?

##  5 Acknowledgements

We thank Qianping Gu for providing the code to find embeddings of projective-
planar graphs [23]. We thank all the anonymous reviewers who have gone through
the draft multiple times minutely and their suggestions which have greatly
enhanced the presentation and the readability of the article.

## References

  * [1] J. Plesník, Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Comenian. Math. 30 (1975) 71–93.
  * [2] D. B. West, Introduction to Graph Theory, 2nd Edition, Prentice Hall, 2000.
  * [3] B. Mohar, C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, 2001\.
  * [4] G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, Journal of Graph Theory 22 (3) (1996) 213–229.
  * [5] W. Goddard, M. A. Henning, Domination in planar graphs with small diameter, Journal of Graph Theory 40 (1) (2002) 1–25.
  * [6] N. Robertson, P. D. Seymour, Graph minors. XX. Wagner’s conjecture, J. Comb. Theory Ser. B 92 (2) (2004) 325–357.
  * [7] D. Archdeacon, A Kuratowski theorem for the projective plane, Journal of Graph Theory 5 (3) (1981) 243–246.
  * [8] G. MacGillivray, K. Seyffarth, Colored homomorphisms of colored mixed graphs, Journal of Combinatorial Theory, Series B 80 (1) (2000) 147–155.
  * [9] P. Hell, J. Nes̆etr̆il, Graphs and homomorphisms, Oxford University Press, 2004.
  * [10] E. Sopena, Homomorphisms and colourings of oriented graphs: An updated survey, Discrete Mathematics 339 (7) (2015) 1993–2005.
  * [11] P. Ochem, A. Pinlou, S. Sen, Homomorphisms of 2-edge-colored triangle-free planar graphs, Journal of Graph Theory 85 (1) (2017) 258–277.
  * [12] N. Alon, T. H. Marshall, Homomorphisms of edge-colored graphs and Coxeter groups, Journal of Algebraic Combinatorics 8 (2015) 5–13.
  * [13] W. Klostermeyer, G. MacGillivray, Analogs of cliques for oriented coloring, Discussiones Mathematicae. Graph Theory 24 (3) (2004) 373–387.
  * [14] J. Bensmail, C. Duffy, S. Sen, Analogous to cliques of (m,n)-colored mixed graphs, Graphs and Combinatorics 33 (2017) 735–750.
  * [15] D. Chakraborty, S. Das, S. Nandi, D. Roy, S. Sen, On clique numbers of colored mixed graphs, Discrete Applied Mathematics 324 (2023) 29–40.
  * [16] R. Naserasr, E. Rovollá, E. Sopena, Homomorphisms of signed graphs, Journal of Graph Theory 79 (3) (2015) 178–212.
  * [17] W. Klostermeyer, G. MacGillivray, Homomorphisms and oriented colorings of equivalence classes of oriented graphs, Discrete Mathematics 274 (2004) 161–172.
  * [18] H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljschr Naturforsch Ges Zürich 88 (1943) 133–142.
  * [19] L. Beaudou, F. Foucaud, R. Naserasr, Homomorphism bounds and edge-colourings of $K_{4}$-minor-free graphs, Journal of Combinatorial Theory, Series B 124 (2017) 128–164.
  * [20] L. Beaudou, F. Foucaud, R. Naserasr, Homomorphism bounds of signed bipartite $K_{4}$-minor-free graphs and edge-colorings of $2k$-regular $K_{4}$-minor-free multigraphs, Discrete Applied Mathematics 261 (2019) 40–51.
  * [21] S. Das, S. Prabhu, S. Sen, A study on oriented relative clique number, Discrete Mathematics 341 (7) (2018) 2049–2057.
  * [22] J. Bensmail, S. Nandi, S. Sen, On oriented cliques with respect to push operation, Discrete Applied Mathematics 232 (2017) 50–63.
  * [23] J. Yu, A practical torus embedding algorithm and its implementation (Masters Thesis, Applied Sciences: School of Computing Science, Simon Fraser University, 2014).