# Intrinsically projectively linked graphs

Joel Foisy, Luis Ángel Topete Galván, Evan Knowles, Uriel Alejandro Nolasco
Yuanyuan Shen, and Lucy Wickham

###### Abstract

A graph is intrinsically projectively linked (IPL) if its every embedding in
projective space contains a nonsplit link. Some minor-minimal IPL graphs have
been found previously [2]. We determine that no minor-minimal IPL graphs on 16
edges exists and identify new minor-minimal IPL graphs by applying $\Delta-Y$
exchanges to $K_{7}-2e$. We prove that for a nonouter-projective-planar graph
$G$, $G+\bar{K}_{2}$ is IPL and describe the necessary and sufficient
conditions on a projective planar graph $G$ such that $G+\bar{K}_{2}$ is IPL.
Lastly, we deduce conditions for $f(G+\bar{K_{2}})$ to have no nonsplit link,
where $G$ is projective planar, $\bar{K_{2}}=\\{w_{0},w_{1}\\}$, and
$f(G+\bar{K_{2}})$ is the embedding onto $\mathbb{R}P^{3}$ with $f(G)$ in
$z=0$, $w_{0}$ above $z=0$, and $w_{1}$ below $z=0$ such that every edge
connecting ${w_{0},w_{1}}$ to $G$ avoids the boundary of the 3-ball, whose
antipodal points are identified to obtain projective space.

††footnotetext: _MSC 2020_ 57M15, 05C10, 57K10

##  1 Introduction

Let $\mathbb{R}P^{2}$ denote real projective plane, which we take to be the
unit disk in $\mathbb{R}^{2}$ with antipodal points on its boundary identified
and let $\mathbb{R}P^{3}$ denote real projective space, which we take to be
the closed unit ball in $\mathbb{R}^{3}$ with antipodal points on its boundary
identified. In $\mathbb{R}P^{3}$, a two component link $L_{1}\cup L_{2}$ is
split if there exists a subset $A$ homeomorphic to a 3-ball, such that
$L_{1}\subset A$, $L_{2}\subset A^{c}$. A graph $G$ is intrinsically linked in
$\mathbb{R}P^{3}$ if in every embedding of $G$ in $\mathbb{R}P^{3}$ there is a
nonsplit two component link. In 1993, Robertson, Seymour and Thomas
characterized the set of all minor-minimal intrinsically linked graphs in
$\mathbb{R}^{3}$: the Petersen family graphs [8]. This family consists of the
seven graphs obtained from $K_{6}$ through a sequence of $\Delta-Y$ and
$Y-\Delta$ exchanges. We wish to obtain a similar result in $\mathbb{R}P^{3}$
and find the complete set of minor-minimal intrinsically projectively linked
(IPL) graphs. All minor-minimal intrinsically linked in ${\mathbb{R}}P^{3}$
signed graphs have been classified [4].

It is known that exactly one graph in the Petersen family, $K_{4,4}-e$, is
intrinsically projectively linked (IPL) [2]. The graph $K_{6}\therefore
K_{6}$, obtained by gluing two copies of $K_{6}$ along three vertices $v_{1}$,
$v_{2}$, $v_{3}$ and then removing the triangle composed of the three edges
between $v_{1}$, $v_{2}$, and $v_{3}$, is also IPL. There are two graphs
obtained by deleting any two edges from $K_{7}$, either the two deleted edges
are adjacent or nonadjacent, we denote either resulting graph as $K_{7}-2e$.
In either case, we show the resulting graph is minor-minimal IPL. All other
known minor-minimal IPL graphs have at least 9 vertices and 17 edges. We
explore candidates for minor-minimal IPL graphs with 8 vertices and 16 edges
by applying $\Delta-Y$ exchanges, that preserve the property of being IPL [2],
to $K_{7}-2e$ and by adding an edge or applying vertex splittings to the
Peterson family graphs. We show there are no new IPL graphs on 16 edges and
classifying IPL graphs on 8 vertices remains open.

A cycle embedded in $\mathbb{R}P^{3}$ is _0-homologous_ if and only if it
bounds a disk. This is also called a null cycle [6]. A cycle embedded in
$\mathbb{R}P^{3}$ is _1-homologous_ if and only if it does not bound a disk.
This is also called an essential cycle [6]. A projective planar graph $G$ is
separating projective planar if for every embedding of $G$ into
$\mathbb{R}P^{2}$, there is a 0-homologous cycle $C$ in $G$ such that one
vertex of $G\setminus C$ is in one connected component of
${\mathbb{R}P}^{2}\setminus C$ and another vertex of $G\setminus C$ is in the
other connected component of $\mathbb{R}P^{2}\setminus C$. If there exists an
embedding of graph $G$ that does not have this property, the graph is
nonseparating projective planar. A separating projective planar graph is
nonouter-projective-planar. We prove that for any nonouter-projective-planar
graph $G$, $G+\overline{K}_{2}$ is IPL by examining the 32 minor-minimal
nonouter-projective-planar graphs and identifying subgraphs of known IPL
graphs [1].

There is no known $n$ for which $K_{n}$ has, in every embedding in projective
space, a nonsplit link with at least one component 0-homologous. It is not
even known if such an $n$ exists. Lastly, we deduce conditions for
$f(G+\bar{K_{2}})$ to have no nonsplit link, where $G$ is projective planar,
$\bar{K_{2}}=\\{w_{0},w_{1}\\}$, and $f(G+\bar{K_{2}})$ is the embedding onto
$\mathbb{R}P^{3}$ with $f(G)$ in $z=0$, $w_{0}$ above $z=0$, and $w_{1}$ below
$z=0$ such that every edge connecting ${w_{0},w_{1}}$ to $G$ avoids the
boundary of the ball whose quotient gives projective space. We show
$f(G+\bar{K_{2}})$ has no nonsplit link of two 0-homologous cycles if and only
if $f(G)$ is a nonseparating projective planar embedding, $f(G+\bar{K_{2}})$
has no nonsplit link of a 0-homologous cycle and a 1-homologous cycle if and
only if $f(G)$ has no separating 1-homologous cycle, and $f(G+\bar{K_{2}})$
has no nonsplit link of two 1-homologous cycles if and only if every
1-homologous edge share a common vertex in $f(G)$ or $f(G)$ has exactly three
1-homologous edges intersecting pairwise.

##  2 Definitions and notation

All of our graphs will be embedded piecewise linearly. Thus, for every graph,
we may assume every cycle intersects the boundary at a finite number of
points.

An embedding of graph in $\mathbb{R}P^{3}$ is an _affine embedding_ if the
graph embedding does not intersect the boundary of the ball we use to define
projective space.

A graph that can be obtained from a graph $G$ by a series of edge deletions,
vertex deletions and edge contractions is called a _minor_ of $G$. The graph
$G$ is _minor-minimal_ if, whenever $G$ has property $P$ and $H$ is a minor of
$G$, then $H$ does not have property $P$. A property $P$ is _minor closed_ if,
whenever a graph $G$ has property $P$ and $H$ is a minor of $G$, then $H$ also
has property $P$. If $P$ is a minor closed property and the graph $G$ does not
have property $P$, then $G$ is a _forbidden graph_ for $P$. Robertson and
Seymour’s Minor Theorem states if $P$ is a minor-closed graph property, then
the minor-minimal forbidden graphs for $P$ form a finite set [8].

An _outer-projective-planar graph_ is one that can be embedded in the
projective plane with all vertices in the same face - this is a minor closed
property. Other minor closed properties include having a nonseparating
projective planar embedding [3], having a planar embedding and having a
linkless embedding in space [2].

Given two graphs $G$, $H$, their _sum_ $G+H$ is formed by starting with the
disjoint union of $G$ and $H$, and adding an edge between every vertex in $G$
and every vertex in $H$. A _complete graph_ is a graph with an edge between
all possible pairs of vertices in the graph. We represent a complete graph as
$K_{m}$, where $m$ is the order of the graph. A _complete bipartite graph_ is
a graph whose vertices can be divided into two disjoint sets, where no two
vertices in the same set are adjacent and every vertex of the first set is
adjacent to every vertex of the second set. We represent a complete bipartite
graph as $K_{n,m}$, where the cardinalities of the two sets are $n$ and $m$. A
_complete $k$-partite graph_ is a graph whose vertices can be divided into $k$
disjoint sets, where no two vertices in the same set are adjacent and every
vertex of a given set is adjacent to every vertex in every other set. We
represent a complete $k$-partite graph as $K_{n_{1},\dots,n_{k}}$, where the
cardinalities of the sets are $n_{1},\dots,n_{k}$.

##  3 Intrinsically projectively linked graphs

###  3.1 $\Delta$-Y, Y-$\Delta$ exchanges

In the first part of this section, we prove that the $Y-\Delta$ exchange
preserves nonseparating projective planarity and that the $\Delta-Y$ exchange
preserves separating projective planarity. The following lemma follows easily
from [6].

######  Lemma 3.1.

Nonprojective-planarity is not always preserved by Y-$\Delta$ exchanges.

###### Proof.

The below graph $C_{11}$ is not projective planar [6]. It has two components,
$A$ and $B$.

Perform a Y-$\Delta$ exchange on the highlighted vertices of $B$, where the
red vertex shares an edge with each of the three green vertices and is taken
to be the center of the Y. Let $B^{\prime}$ denote the resulting graph.
Subgraph $A$ is projective planar and subgraph $B^{{}^{\prime}}$ is planar.
Therefore, the resulting graph $C_{11}^{{}^{\prime}}$ is projective planar.

Figure 1: Subgraph $B^{{}^{\prime}}$ from a Y-$\Delta$ on $B$

Figure 2: Embedding of $C_{11}^{{}^{\prime}}$ in $\mathbb{R}P^{2}$

∎

######  Corollary 3.1.

Projective planarity is not always preserved by $\Delta$-Y exchanges.

######  Theorem 3.1.

Nonseparating projective planarity is preserved by Y-$\Delta$ exchanges.

###### Proof.

Let $G$ have a nonseparating embedding with Y having vertices $v_{0}$,
$v_{1}$, $v_{2}$ and $v_{3}$ and perform a Y-$\Delta$ exchange. By ambient
isotopy, we may assume that the exchange takes place inside a sufficiently
small neighbourhood $U$ of $v_{0}$ that contains only $v_{1}$, $v_{2}$,
$v_{3}$. Since $U$ is bounded by a 0-homologous cycle, we may assume that $U$
is affine. Note that the Y-$\Delta$ exchange preserves projective planarity,
and name the resulting embedding $G^{\prime}$.

Suppose to the contrary that $G^{\prime}$ has a separating cycle $C^{\prime}$.
There are four cases to consider:

  1. 1.

$C^{\prime}$ shares zero edges with
${(v_{1},v_{2}),(v_{1},v_{3}),(v_{2},v_{3})}$
Then $U$ lies on one side of $C^{\prime}$. Suppose that $C^{\prime}$ separates
$v_{i},v_{j}$ in $G^{\prime}$, we must have $v_{i},v_{j}$ lies on two sides of
$C^{\prime}$ in $G$. Therefore $C^{\prime}$ separates $v_{i},v_{j}$ in $G$,
this is a contradiction.

  2. 2.

$C^{\prime}$ shares one edge with
${(v_{1},v_{2}),(v_{1},v_{3}),(v_{2},v_{3})}$
Without loss of generality suppose $C^{\prime}$ consists of
$L_{1}=(v_{1},v_{2})$ and $L_{2}=C^{\prime}\setminus L_{1}$. Let $C$ be the
cycle in $G$ consisting of $(v_{0},v_{1})$, $(v_{0},v_{2})$ and $L_{2}$.
Suppose $C^{\prime}$ separates $v_{i},v_{j}$ in $G^{\prime}$, then $C$
separates $v_{i},v_{j}$ in $G$, which is a contradiction.

  3. 3.

$C^{\prime}$ shares two edges with
${(v_{1},v_{2}),(v_{1},v_{3}),(v_{2},v_{3})}$
Without loss of generality suppose $C^{\prime}$ consists of
$L_{1}=v_{1}\cup(v_{1},v_{2})\cup(v_{1},v_{3})$ and $L_{2}=C^{\prime}\setminus
L_{1}$. Let $C$ be the cycle in $G$ consisting of $(v_{0},v_{2})$,
$(v_{0},v_{3})$ and $L_{2}$. Suppose $C^{\prime}$ separates $v_{i},v_{j}$ in
$G^{\prime}$, then $v_{i},v_{j}$ lie on the other side of $U$. Therefore $C$
separates $v_{i},v_{j}$ in $G$, which is a contradiction.

  4. 4.

$C^{\prime}$ shares 3 edge with ${(v_{1},v_{2}),(v_{1},v_{3}),(v_{2},v_{3})}$
Then $C^{\prime}$ is the cycle consisting of
${(v_{1},v_{2}),(v_{1},v_{3}),(v_{2},v_{3})}$. However, by assumption $U$
contains no other vertex, hence $C^{\prime}$ cannot be a separating cycle.

∎

######  Corollary 3.2.

Given a particular $\Delta$-Y exchange that preserves projective planarity of
$G$, this $\Delta$-Y exchange preserves separating projective planarity on G.

###### Proof.

Suppose $G$ is a separating projective planar graph. Name the graph after the
$\Delta$-Y exchange to be $G^{\prime}$. Since the Y-$\Delta$ exchanges
preserve projective planarity, every embedding of $G^{\prime}$ is obtained
from a separating embedding of $G$ via a $\Delta$-Y exchange on the projective
plane. The result then follows. ∎

###  3.2 $K_{7}-2e$

To find a new minor-minimal IPL graph, we performed $\Delta-Y$ exchanges on
$K_{7}-2e$ in attempt to find a graph that is IPL that does not contain
$K_{7}-2e$ or $K_{4,4}-e$ as a minor.

Up to symmetry there are two cases of removing two edges from $K_{7}$: the two
edges being adjacent (Case 1) or nonadjacent (Case 2). Consider performing a
$\Delta-Y$ exchange on a triangle in $K_{7}-2e$. By symmetry there are three
cases: the triangle has no vertex with its edge removed from $K_{7}$, has 1
vertex with its edge removed, or has 2 vertices with their edges removed.

Figure 3: Two cases of removing two edges from $K_{7}$

######  Theorem 3.2.

The below table summarizes the results, where a indicates that a new minor-
minimal intrinsically linked graph exists.

# vertices with edges removed | 0 | 1 | 2
---|---|---|---
Case 1 |  |  |
Case 2 |  |  |

###### Proof.

Note that a graph resulting from performing a $\Delta-Y$ exchange on a
$K_{7}-2e$ does not contain a $K_{7}-2e$ as a minor. Therefore it suffices to
check whether the resulting graph contains $K_{4,4}-e$, the only known IPL
graph on 8 vertices, as a minor. Take the two vertex sets of $K_{4,4}-e$ to be
$V_{0}$, $V_{1}$ and separately consider different cases.

####  3.2.1 Case 1

In Case 1, the two edges removed from $K_{7}$ are adjacent. The $\Delta-Y$
exchange can be performed on four types of triangles in $K_{7}-2e$.

Figure 4: (a) The $\Delta-Y$ exchange performed on a triangle that has zero
vertices with an edge removed (b) The $\Delta-Y$ exchange performed on a
triangle that has one vertex with an edge removed (c) The $\Delta-Y$ exchange
performed on a triangle that has one vertex with an edge removed (d) The
$\Delta-Y$ exchange performed on a triangle that has two vertices with an edge
removed

  * •

Triangle has no vertex with an edge removed, as in Figure 4 (a).

Without loss of generality suppose the triangle has vertices
${v_{3},v_{4},v_{6}}$. Consider $V_{0}=\\{v_{1},v_{2},v_{7},v_{8}\\}$ and
$V_{1}=\\{v_{3},v_{4},v_{5},v_{6}\\}$, then the resulting graph contains a
minor of $K_{4,4}-e$.

  * •

Triangle has exactly one vertex $v$ with an edge removed. There are two sub-
cases as in Figure 4 (b), (c).

Note that $v_{8}$ in the resulting graph has degree three, and corresponds to
a degree three vertex in $K_{4,4}-e$ if the graph contains a minor of
$K_{4,4}-e$. Therefore if $v_{i}$, $v_{j}$ are not connected by an edge, where
$1\leq i,j\leq 7$, they are in different vertex sets.

    * –

$v$ has one edge removed

Without loss of generality suppose the triangle has vertices
$v_{2},v_{4},v_{5}$. Since no edge connects $v_{7}$ with $v_{1}$, $v_{1}$ with
$v_{2}$, $v_{2}$ with $v_{4}$, and $v_{4}$ with $v_{5}$, then $v_{7}$,
$v_{1}$, $v_{2}$, $v_{4}$, $v_{5}$ must be in the same vertex set. This is a
contradiction since a vertex set has four vertices. There is a new IPL graph
in this case.

    * –

$v$ has two edges removed

Without loss of generality suppose the triangle has vertices
$v_{1},v_{4},v_{5}$. Since no edge connects $v_{1}$ with $v_{2}$, $v_{1}$ with
$v_{4}$, $v_{1}$ with $v_{5}$, and $v_{1}$ with $v_{7}$, then $v_{1}$,
$v_{2}$, $v_{4}$, $v_{5}$, $v_{7}$ must be in the same vertex set. This is a
contradiction since a vertex set has four vertices. There is a new IPL graph
in this case.

  * •

Triangle has two vertices with an edge removed, as in Figure 4 (d).

Without loss of generality suppose the triangle has vertices
${v_{2},v_{6},v_{7}}$. Consider $V_{0}=\\{v_{1},v_{2},v_{6},v_{7}\\}$ and
$V_{1}=\\{v_{3},v_{4},v_{5},v_{8}\\}$, then the resulting graph contains a
minor of $K_{4,4}-e$.

####  3.2.2 Case 2

In Case 2, the two edges removed from $K_{7}$ are nonadjacent.

Figure 5: (a) The $\Delta-Y$ exchange performed on a triangle that has zero
vertices with an edge removed (b) The $\Delta-Y$ exchange performed on a
triangle that has one vertex with an edge removed (c) The $\Delta-Y$ exchange
performed on a triangle that has two vertices with an edge removed

  * •

Triangle has zero vertices with an edge removed, as in Figure 5 (a).

Without loss of generality suppose the triangle has vertices
$v_{5},v_{6},v_{7}$. Since no edge connects $v_{5}$ with $v_{6}$ and $v_{6}$
with $v_{7}$, $v_{5}$, $v_{6}$, $v_{7}$ are in the same vertex set. Similarly
$v_{1}$ and $v_{2}$, $v_{3}$ and $v_{4}$ are in the same vertex set. Since a
vertex set has four vertices, it must be that
$V_{0}=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and
$V_{1}=\\{v_{5},v_{6},v_{7},v_{8}\\}$. However, $v_{8}$ does not connect to
any vertex in $V_{0}$. Therefore the graph does not contain a minor of
$K_{4,4}-e$. There is a new IPL graph in this case.

  * •

Triangle has one vertex with an edge removed, as in Figure 5 (b).

Without loss of generality suppose the triangle has vertices
${v_{4},v_{6},v_{7}}$. Consider $V_{0}=\\{v_{1},v_{2},v_{5},v_{8}\\}$ and
$V_{1}=\\{v_{3},v_{4},v_{6},v_{7}\\}$, then the resulting graph contains a
minor of $K_{4,4}-e$.

  * •

Triangle has two vertices with an edge removed, as in Figure 5 (c).

Without loss of generality suppose the triangle has vertices
$v_{1},v_{3},v_{6}$. Since no edge connects $v_{1}$ with $v_{2}$, $v_{1}$ with
$v_{3}$, $v_{1}$ with $v_{6}$, and $v_{3}$ with $v_{4}$, then $v_{1}$,
$v_{2}$, $v_{3}$, $v_{4}$, $v_{6}$ must be in the same vertex set. This is a
contradiction since a vertex set has four vertices. There is a new IPL graph
in this case.

∎

###  3.3 Irreducible graphs

A graph $G$ is irreducible for a surface $M$ if $G$ does not embed into $M$
and every proper subgraph of $G$ embeds into $M$. There are 103 irreducible
graphs for the projective plane [6].

######  Theorem 3.3.

If a graph $G$ is irreducible for the projective plane, then it has an
embedding in projective space with no a nonsplittable 2-link containing at
least one 0-homologous component.

######  Proof.

Since $G$ is irreducible, there exists a projective planar embedding of $G-e$.
Suppose this embedding lies on $z=0$ and add $e$ onto this embedding in
projective space. This is the only edge not on $z=0$ and it lies above all
other edges, hence this embedding does not have a link with a 0-homologous
cycle.

###  3.4 $G+\overline{K_{2}}$

######  Lemma 3.2 (Bustamante et al [2]).

Let G=($P_{1}\cup P_{2}$)$\backslash$ $\\{(v_{1},v_{2})\\}$ be a graph, where
$P_{1},P_{2}$ are graphs in the Petersen family and $V(P_{1}\cap
P_{2})=\\{v_{1},v_{2}\\}.$ Then $G$ is IPL.

If a connected graph $G$ is _$k$ -connected_, then $G$ must have more than $k$
vertices and it remains connected whenever fewer than $k$ vertices are
removed. The _$k$ -connectivity_ of a graph is the maximum $k$ for which the
graph is _$k$ -connected_.

######  Lemma 3.3 (Bustamante et al [2]).

There are 18 IPL graphs with 3-connectivity that can be obtained from
$K_{6}\therefore K_{6}$ by $\Delta$-$Y$ exchanges.

######  Proposition 3.1.

Let $G$ be a nonouter-projective-planar graph. Then $G+\overline{K_{2}}$ is
IPL.

###### Proof.

Given G nonouter-projective-planar graph, it must contain one of the 32 minor-
minimal nonouter-projective-planar graph as a minor [1], so it is sufficient
to prove these special cases. In the following graphs, the idea is to prove
that $K_{4,4}-e$ is a minor, so red vertices will indicate the vertices that
belong to a set of $K_{4,4}-e$ and green vertices belong to the other set. The
vertices will be labeled with a number that indicates the number of edges that
a vertex shares with the vertices of the other set. In addition, vertices with
no edges drawn are the vertices of $\overline{K_{2}}$ and they are supposed to
be connected to the rest of the vertices of $G$, but their edges have not been
drawn in order to have a more understandable drawing.

Figure 6: $\kappa_{1}+\overline{K_{2}}$

Figure 7: $\theta_{1}+\overline{K_{2}}$

Figure 8: $\zeta_{1}+\overline{K_{2}}$

Figure 9: $\eta_{1}+\overline{K_{2}}$

Figure 10: $\gamma_{1}+\overline{K_{2}}$

Figure 11: $\delta_{1}+\overline{K_{2}}$

Figure 12: $\epsilon_{1}+\overline{K_{2}}$

For the cases of $\alpha_{1}$ and $\beta_{2}$ graphs, we use lemmas mentioned
at the beginning of this subsection. Let $G_{1}=(K_{6}\cup
K_{6})\backslash\\{(e,f)\\}$ be a graph, where $V(K_{6}\cap K_{6})=\\{e,f\\},$
and $G_{2}=K_{6}\therefore K_{6}.$

Figure 13: $G_{1}$ and $\alpha_{1}+\overline{K_{2}}$ Figure 14: $G_{2}$ and
$\beta_{1}+\overline{K_{2}}$

By the labeling, we see that $G_{1}$ is a minor of
$\alpha_{1}+\overline{K_{2}}$ and $G_{2}$ is a minor of
$\beta_{1}+\overline{K_{2}},$ so $\alpha_{1}+\overline{K_{2}}$ and
$\beta_{1}+\overline{K_{2}}$ are IPL. Thus, by using $\Delta$-$Y$ exchanges,
the rest of the graphs in the families will also be IPL.

∎

###  3.5 Conditions for $G+\bar{K_{2}}$ to have no nonsplit links of different
types

It is an open question to determine the smallest $n$ such that $K_{n}$ has a
nonsplit link with a 0 homologous cycle in every embedding into projective
space. In this section we discuss conditions on an embedding of
$G+\bar{K_{2}}$ to have no nonsplit links of a certain homology type.

Throughout this section, consider $G$, a connected graph with a projective
planar embedding $f(G)$. Let $\bar{K_{2}}$ have the vertex set
$\\{w_{0},w_{1}\\}$. Take $f(G+\bar{K_{2}})$ to be the embedding onto
$\mathbb{R}P^{3}$ with $f(G)$ in $z=0$, $w_{0}$ above $z=0$, and $w_{1}$ below
$z=0$ such that every edge connecting ${w_{0},w_{1}}$ to $G$ does not cross
the boundary and is straight. Let an edge be 0-homologous if it crosses the
boundary an even number of times, and let an edge be 1-homologous if it
crosses the boundary an odd number of times.

We deduce the necessary and sufficient conditions for $f(G+\bar{K_{2}})$ to
have no nonsplit link by proving $f(G+\bar{K_{2}})$ has no nonsplit link of
two 0-homologous cycles if and only if $f(G)$ is a nonseparating projective
planar embedding, $f(G+\bar{K_{2}})$ has no nonsplit link of a 0-homologous
cycle and a 1-homologous cycle if and only if $f(G)$ has no separating
1-homologous cycle or a 1-homologous cycle with vertices on both sides, and
$f(G+\bar{K_{2}})$ has no nonsplit link of two 1-homologous cycles if and only
if every 1-homologous edge share a common vertex in $f(G)$ or $f(G)$ has
exactly three 1-homologous edges intersecting pairwise.

Figure 15: $f(G+\bar{K_{2}})$

Since ambient isotopy preserves split and nonsplit links, assume that no
vertex of $f(G+\bar{K_{2}})$ lies on the boundary. Assume also that in
$f(G+\bar{K_{2}})$, no loop exists and at most one edge connects any two
vertices.

####  3.5.1 Nonsplit links between two 0-homologous cycles

The properties of separating and nonseparating projective planar graphs are
very helpful in characterizing links in projective space. The theorems in this
section reveal more about this relationship. We have written a related paper
where we characterized many members of the set of minor-minimal separating
projective planar graphs [5].

######  Theorem 3.4.

The embedding $f(G+\bar{K_{2}})$ has no nonsplit link of two 0-homologous
cycles if and only if $f(G)$ is a nonseparating projective planar embedding.

######  Proof.

Suppose there is a nonsplit link $L$ consisting of two components $C_{1}$,
$C_{2}$. Note that if $w_{0}$, $w_{1}$ are not in the same component of $L$,
$L$ must be split. Without loss of generality assume that $C_{1}$ has the form
$(w_{0},a_{1},...,a_{n},w_{1},b_{1},...b_{m})$, where $n,m\in\mathbb{Z^{+}}$
and $C_{2}$ lies on $z=0$. Note that all $a_{i}$ lie on the same side of
$C_{2}$ on $z=0$, and all $b_{i}$ lie on the same side of $C_{2}$ on $z=0$.

If $a_{i}$, $b_{i}$ lie on the same side of $C_{2}$, $L$ is split. If $a_{i}$,
$b_{i}$ lie on different sides of $C_{2}$, then $C_{2}$ is a separating cycle
in the projective planar embedding of $G$. In either case we have a
contradiction.

Conversely, suppose $f(G)$ is a separating projective planar embedding, then
there exists a cycle $C_{0}$ separating $v_{0}$, $v_{1}$. Consider the link
$L$ consisting of $C_{0}$ and $C_{1}=(v_{0},w_{0},v_{1},w_{1})$, then $L$ is a
nonsplit link of two 0-homologous cycles, contradicting the assumption.

######  Corollary 3.3.

If $G$ is a nonseparating projective planar graph, then $G+\bar{K_{2}}$ has an
embedding with no link consisting of two 0-homologous cycles.

####  3.5.2 Nonsplit links between one 0-homologous cycle and one 1-homologous
cycle

Consider a projective planar embedding $f(G)$ of $G$ and a 0-homologous cycle
bounding $f(G^{\prime})\subset f(G)$ which contains every vertex of $f(G)$ as
in Figure 16. Then each 1-homologous cycle divides $f(G^{\prime})$ into two
sides. A 1-homologous cycle is separating if there is at least one vertex on
each of its two sides.

Figure 16: Separating 1-homologous Cycle

######  Theorem 3.5.

Given that $f(G)$ is nonseparating, $f(G+\bar{K_{2}})$ has no nonsplit link of
a 0-homologous cycle and a 1-homologous cycle if and only if $f(G)$ has no
separating 1-homologous cycle

######  Proof.

The two lemmas below complete the proof.

######  Lemma 3.4.

Suppose $f(G+\bar{K_{2}})$ has a nonsplit link of a 0-homologous cycle and a
1-homologous cycle, then one of the following two cases occurs

  1. 1.

$f(G)$ has a separating 1-homologous cycle

  2. 2.

$f(G)$ is a separating projective planar embedding

######  Proof.

Suppose there is a nonsplit link $L$ consisting of two components $C_{0}$,
$C_{1}$, where $C_{0}$ is 0-homologous and $C_{1}$ is 1-homologous. Note that
if $w_{0}$, $w_{1}$ are not in the same component of $L$, then $L$ must be
split. Then one of the following two cases occurs

  1. 1.

$w_{0}$, $w_{1}$ in $C_{0}$

Without loss of generality assume that $C_{0}$ has the form
$(w_{0},a_{1},...,a_{n},w_{1},$ $b_{1},...b_{m})$, where
$n,m\in\mathbb{Z^{+}}$. Note that all $a_{i}$ lie on the same side of $C_{1}$
on $z=0$, and all $b_{i}$ lie on the same side of $C_{1}$ on $z=0$. If
$a_{i}$, $b_{i}$ lie on the same side of $C_{1}$, $L$ is split. If $a_{i}$,
$b_{i}$ lie on different sides of $C_{1}$, then $C_{1}$ is a separating
1-homologous cycle.

  2. 2.

$w_{0}$, $w_{1}$ in $C_{1}$

Without loss of generality assume that $C_{1}$ has the form
$(w_{0},a_{1},...,a_{n},w_{1},$ $b_{1},...b_{m})$, where
$n,m\in\mathbb{Z^{+}}$. Note that all $a_{i}$ lie on the same side of $C_{1}$
on $z=0$, and all $b_{i}$ lie on the same side of $C_{1}$ on $z=0$. If
$a_{i}$, $b_{i}$ lie on the same side of $C_{1}$, $L$ is split. If $a_{i}$,
$b_{i}$ lie on different sides of $C_{1}$, then $C_{0}$ is a separating
0-homologous cycle, and $f(G)$ is a separating projective planar embedding.

######  Lemma 3.5.

Suppose $f(G)$ has a separating 1-homologous cycle, then $f(G+\bar{K_{2}})$
has a nonsplit link of a 0-homologous cycle and a 1-homologous cycle.

######  Proof.

Consider a 1-homologous cycle $C_{1}$ separating $v_{0}$, $v_{1}$. Consider
the link $L$ consisting of $C_{1}$ and $C_{0}=(v_{0},w_{0},v_{1},w_{1})$, then
$L$ is a nonsplit link of the 0-homologous cycle $C_{0}$ and the 1-homologous
cycle $C_{1}$.

####  3.5.3 Nonsplit links between two 1-homologous cycles

######  Theorem 3.6.

The embedding $f(G+\bar{K_{2}})$ has no nonsplit link of two 1-homologous
cycles if and only if every pair of 1-homologous edges share a common vertex
in $f(G)$, if and only if exactly one of the two following occurs

  1. 1.

Every 1-homologous edge shares a common vertex $v_{0}$ in $f(G)$.

  2. 2.

The embedding $f(G)$ has exactly three 1-homologous edges intersecting
pairwise.

Figure 17: Case 1 and Case 2, where $f(G^{\prime})$ is planar

###### Proof.

We separately prove each statement of the theorem.

  * •

Every pair of 1-homologous edges share a common vertex implies no link of two
1-homologous cycles.

Every 1-homologous cycle contains a 1-homologous edge in $f(G)$. Therefore
every two 1-homologous cycle intersects, and there is no link of two
1-homologous cycles.

  * •

A pair of 1-homologous edges does not share a common vertex implies a link of
two 1-homologous cycles exists.

Consider the edges between $v_{0}$, $v_{1}$ and $u_{0}$, $u_{1}$ to be the
pair of 1-homologous edges. Then the cycles $C_{0}$ consisting of
$(v_{0},v_{1})$, $(v_{1},w_{0})$, $(w_{0},v_{0})$ and $C_{1}$ consisting of
$(u_{0},u_{1})$, $(u_{1},w_{1})$, $(w_{1},u_{0})$ form the desired link.

  * •

Case 1 or Case 2 implies every pair of 1-homologous edges share a common
vertex in $f(G)$.

Note that in either case, every pair of 1-homologous edges share a common
vertex in $f(G)$.

  * •

Every pair of 1-homologous edges share a common vertex in $f(G)$ implies Case
1 or Case 2.

Suppose not every 1-homologous edge passes through a common vertex, then there
exists three 1-homologous edges that do not pass through a common vertex but
intersect pairwise at $v_{0}$, $v_{1}$, $v_{2}$. Suppose there is a fourth
1-homologous edge, then one of the following three cases must occur

  1. 1.

This edge connects two of $v_{0}$, $v_{1}$, $v_{2}$.

Without loss of generality suppose it connects $v_{0}$, $v_{1}$. Then there
are two 1-homologous edges between $v_{0}$, $v_{1}$, contradicting
multiplicity.

  2. 2.

This edge connects one of $v_{0}$, $v_{1}$, $v_{2}$ to a new vertex $u_{0}$.

Without loss of generality suppose it connects $v_{0}$, $u_{0}$. Then the pair
of 1-homologous edges of $(v_{0},u_{0})$ and $(v_{1},v_{2})$ does not share a
common vertex, contradicting the assumption.

  3. 3.

This edge connects two new vertices $u_{0}$, $u_{1}$.

The pair of 1-homologous edges of $(v_{0},v_{1})$ and $(u_{0},u_{1})$ does not
share a common vertex, contradicting the assumption.

Therefore there cannot be a fourth 1-homologous edge, and Case 2 must occur.

∎

######  Corollary 3.4.

If $f(G+\bar{K_{2}})$ has no nonsplit link of two 1-homologous cycles, then
$G$ is a planar graph.

###### Proof.

Consider Case 1 and Case 2 separately

  * •

Case 1: Every 1-homologous edge shares a common vertex $v_{0}$ in $f(G)$

Figure 18: $G$ is planar

Suppose every 1-homologous edge is in the form $(v_{0},u_{i})$,
$i\in\mathbb{Z}^{+}$ and let the set of 1-homologous edges be $V_{1}$. We
claim $f(G)$ has an alternative embedding $f^{\prime}(G)$ where $f(G\setminus
V_{1})$ is unchanged and each edge incident to $v_{0}$ does not cross the
boundary. Construct $f^{\prime}(G)$ by inductively adding edges incident to
$v_{0}$ not crossing the boundary to $f(G\setminus V_{1})$ as in Figure 18.

Consider an affine embedding of $f(G\setminus V_{1})$ and let $F$ be the face
containing the boundary of projective space. Note that $v_{0}$, $u_{i}$ all
lie on the boundary of $F$. Since $v_{0}$, $u_{1}$ both lie on the affine
boundary of a common face $F$, an edge between $v_{0}$, $u_{1}$ not crossing
the boundary can be added. Either $(v_{0},u_{1})$ divides $F$ into two faces,
each having an affine boundary and having $v_{0}$ lying on its boundary, or
$(v_{0},u_{1})$ does not divide $F$ into two faces, with $F$ having an affine
boundary and having $v_{0}$ lying on its boundary. Inductively note that each
pair $v_{0}$, $u_{i}$ lie on the affine boundary of a common face, therefore
an edge connecting $v_{0}$, $u_{i}$ not crossing the boundary can be added.
The new edge divides the common face into two faces, each having an an affine
boundary and having $v_{0}$ lying on its boundary.

The resulting embedding is planar.

  * •

Case 2: The embedding $f(G)$ has exactly three 1-homologous edges intersecting
pairwise

Consider the alternative planar embedding of $G$ illustrated below.

Figure 19: $G$ is planar

∎

By considering Theorem 3.4, Theorem 3.5, Theorem 3.6, we attempt to deduce all
possible forms of $f(G)$ such that $f(G+\bar{K_{2}})$ has no nonsplit link.

####  3.5.4 Case 1

Assume $f(G)$ has the embedding as in Case 1, then $f(G+\bar{K_{2}})$ has no
link between two 1-homologous cycles. It suffices to look at links between two
0-homologous cycles and between one 0-homologous and one 1-homologous cycle.

######  Theorem 3.7.

Assume $f(G)$ has the embedding as in Case 1. Let $V_{0}$ be the set of
0-homologous edges connecting to $v_{0}$, and $V_{1}$ be the set of
1-homologous edges connecting to $v_{0}$. The embedding $f(G+\bar{K_{2}})$ has
no nonsplit link of two 0-homologous cycles if and only if $f(G\setminus
V_{0})$ and $f(G\setminus V_{1})$ are equivalent to nonseparating planar
embeddings.

######  Proof.

Note that $f(G\setminus V_{1})$ is an affine embedding, and $f(G\setminus
V_{0})$ can be isotoped to an affine embedding. Suppose $f(G\setminus V_{0})$
or $f(G\setminus V_{1})$ has a separating cycle, then $f(G)$ has a separating
cycle. By Theorem 3.4, $f(G+\bar{K_{2}})$ has a nonsplit link of two
0-homologous cycles.

Conversely, assume $f(G\setminus V_{0})$ and $f(G\setminus V_{1})$ are
equivalent to nonseparating planar embeddings. Suppose $f(G+\bar{K_{2}})$ has
a nonsplit link of two 0-homologous cycles, then $f(G)$ is a separating
projective planar embedding and has a separating cycle $C$. Note that $C$
either has no 1-homologous edge or has two 1-homologous edges. If $C$ has no
1-homologous edge, then $f(G\setminus V_{1})$ is a separating planar
embedding. If $C$ has two 1-homologous edges, then $f(G\setminus V_{0})$ can
be isotoped to a separating affine embedding. In both cases we have a
contradiction.

####  3.5.5 Case 2

Assume $f(G)$ has the embedding as in Case 2, then $f(G+\bar{K_{2}})$ has no
link between two 1-homologous cycles. It suffices to look at links between two
0-homologous cycles and between one 0-homologous and one 1-homologous cycle.

######  Theorem 3.8.

Assume $f(G)$ has the embedding as in Case 2. Let the set of 1-homologous
edges be $(v_{0},v_{1})$, $(v_{1},v_{2})$, and $(v_{2},v_{0})$. The embedding
$f(G+\bar{K_{2}})$ has no nonsplit link of two 0-homologous cycles if and only
if $f(G\setminus(v_{0},v_{1}))$, $f(G\setminus(v_{1},v_{2}))$ and
$f(G\setminus(v_{2},v_{0}))$ are equivalent to nonseparating planar
embeddings.

######  Proof.

Suppose $f(G\setminus(v_{0},v_{1}))$, $f(G\setminus(v_{1},v_{2}))$ and
$f(G\setminus(v_{2},v_{0}))$ has a separating cycle, then $f(G)$ has a
separating cycle. By Theorem 3.4, $f(G+\bar{K_{2}})$ has a nonsplit link of
two 0-homologous cycles.

Suppose $f(G+\bar{K_{2}})$ has a nonsplit link of two 0-homologous cycles,
then $f(G)$ is a separating projective planar embedding and has a separating
cycle $C$. Note that $C$ either has no 1-homologous edge or has two
1-homologous edges. If $C$ has no 1-homologous edge, then
$f(G\setminus\\{(v_{0},v_{1}),(v_{1},v_{2}),(v_{2},v_{0})\\})$ is a separating
planar embedding. If $C$ has two 1-homologous edges, then one of
$f(G\setminus(v_{0},v_{1}))$, $f(G\setminus(v_{1},v_{2}))$ and
$f(G\setminus(v_{2},v_{0}))$ is a separating planar embedding. In both cases
we have a contradiction.

######  Note.

Dehkordi and Farr [3] showed that every nonseparating planar graph is an
outerplanar graph, a wheel graph, or an elongated triangular prism graph. We
can then separately look at cases where $f(G\setminus V_{0})$, $f(G\setminus
V_{1})$, $f(G\setminus(v_{0},v_{1}))$, $f(G\setminus(v_{1},v_{2}))$ and
$f(G\setminus(v_{2},v_{0}))$ are outerplanar, wheel, or elongated triangular
prism.

###  3.6 IPL graphs on 16 edges

There is one minor-minimal IPL graph with 15 edges, which is $K_{4,4}-e$ [2].
We examined the other Petersen family graphs with one added edge or one vertex
splitting to search for a minor-minimal IPL graph on 16 edges. The details of
this examination follow. We found no new minor-minimal IPL graphs on 16 edges.
We declined to examine possible minor-minimal IPL graphs on 17 or more edges.

Since $K_{6}$ is not IPL and $K_{7}-2e$ is minor minimal IPL, there is no
other IPL graphs with seven or fewer vertices. However, classifying all minor-
minimal IPL graphs on 8 (or more) vertices remains open.

Here we show every graph that results from a Petersen family graph with either
one added edge or one vertex splitting. This makes the graphs have 16 edges.
Every graph here is either not a minor-minimal IPL graph, or contains
$K_{4,4}-e$ as a minor, and this shows there is no minor-minimal IPL graph on
16 edges.

Figure 20: The Petersen family graphs on the projective plane. Image from [3],
which was inspired by K. Kawarabayashi et al [7].

####  3.6.1 Adding an edge

We will add one edge to each of the Petersen family graphs and determine if
the resulting graph is minor-minimally IPL.

First, consider graph $K_{6}$(A). No edge can be added to this graph because
it is a complete graph.

Now, consider graph $P_{7}$(B) and $K_{3,3,1}$(C). The graph $K_{7}-2e$ is
also minor-minimally IPL [2]. This graph has seven vertices and 19 edges. This
means that there is no IPL graph with seven vertices and less than 19 edges.
Thus, we do not need to examine the graphs $P_{7}$ and $K_{3,3,1}$ for IPL
graphs on 16 edges, as both have seven vertices.

Now, consider graph $P_{8}$(E). The graph $P_{8}$ contains three vertices of
degree 3, four vertices of degree 4, and one vertex of degree 5. One of the
vertices of degree 3, vertex 6, is not equivalent to the others under any
graph automorphism as in Figure 22. This vertex is already connected to
vertices 5, 7, and 8. If we connect vertex 6 to the remaining vertices, the
graph remains projective planar. The remaining two vertices of degree 3 are
equivalent, so without loss of generality, we have chosen vertex 7. This
vertex is already connected to vertices 1, 3, and 6. If we connect vertex 6 to
the remaining vertices, the graph remains projective planar, as seen in Figure
22.

Figure 21: Vertex 6 connected

Figure 22: Vertex 7 connected

The vertices of degree 4 are equivalent, so without loss of generality, we
have chosen vertex 1. It is already connected to vertices 2, 4, 7, and 8. If
we connect vertex 1 to the remaining vertices, the graph remains projective
planar, as seen in Figure 24. There is one vertex of degree 5, which is vertex
8. It is already connected to 1, 2, 3, 4, and 6. If we connect it to 5 and 7,
the graph remains projective planar, as seen in Figure 24. Thus, adding one
edge to $P_{8}$ will not create a minor-minimally IPL graph.

Figure 23: Vertex 1 connected

Figure 24: Vertex 8 connected

Now, consider graph $P_{9}$(F). In $P_{9}$, there are six vertices of degree 3
and three vertices of degree 4. The vertices of degree 3 are all equivalent,
so without loss of generality, we have chosen vertex 1. This vertex is already
connected to vertices 2, 4, and 9. If we add an edge from vertex 1 to any of
the remaining vertices, the graph will remain projective planar, as seen in
Figure 27. Now consider the vertices of degree 4. They are all equivalent, so
without loss of generality, we have chosen vertex 4. This vertex is already
connected to vertices 1, 5, 6, and 7. As seen in the drawing, if we add an
edge from vertex 4 to any of the remaining vertices, the graph will remain
projective planar, as seen in Figure 27. Thus, adding one edge to $P_{9}$ will
not create a minor-minimally IPL graph.

Figure 25: Vertex 1 connected

Figure 26: Vertex 4 connected

Figure 27: Vertex 1 connected

Finally, consider graph $P_{10}$(G). Every vertex on this graph has degree 3,
and they are all equivalent. Without loss of generality, we have chosen vertex
1. This vertex is already connected to vertices 2, 5, and 6. If we add an edge
from vertex 1 to any of the remaining vertices, the graph will remain
projective planar, as seen in Figure 27. Thus, adding one edge to $P_{10}$
will not create a minor-minimally IPL graph.

####  3.6.2 Splitting a vertex

Vertex splitting is the opposite of edge contraction. When splitting a vertex,
the edges from that vertex are divided into two groups - the edges that will
remain connected to the old vertex and the edges that will be moved and now
connect to the new vertex. Splitting a vertex of degree 3 means that one of
these groups will have only one edge in it. This results in a graph that is
homeomorphic to the original graph. The original graphs are all projective
planar, and the homeomorphic graphs will also have this property. Thus, for
the vertices of degree 3 we know the graphs that result from their vertex
splitting will not be IPL.

First, consider graph $K_{6}$(A). Every vertex splitting of $K_{6}$ will
create a graph on seven vertices. The only minor-minimal IPL graph on seven
vertices are $K_{7}-2e$, which have 19 edges.

Now, consider graph $P_{7}$(B). This graph has one vertex of degree 3, three
vertices of degree 4, and three vertices of degree 5. We consider the vertices
of degree 4. They are all equivalent. Without loss of generality, we have
chosen vertex 7. Assign numbers to its adjacent edges: edge 1 connects vertex
7 to vertex 1, edge 2 connects vertex 7 to vertex 2, edge 3 connects vertex 7
to vertex 3, and edge 4 connects vertex 7 to vertex 5, as in Figure 28.

Figure 28: Graph $P_{7}$ with the edges incident to vertex 7 labelled.

Cases 1: Suppose three of the four edges connect to the new vertex. This will
create a homeomorphic graph, so this case will create a projective planar
graph.

Case 2: Suppose two edges that bound the same region connect to the new
vertex. This case will create a projective planar graph, as seen in Figure 31.

Case 3: Suppose two edges that do not bound the same regions, one of which
connects to a degree 3 vertex, are connected to the new vertex. This first
embedding is not projective planar, as seen in Figure 31. However, there is
another embedding that is projective planar, as seen in Figure 31, so this
case does not create an IPL graph.

Figure 29: Case 2 embedding

Figure 30: Case 3 Embedding 1

Figure 31: Case 3 Embedding 2

Case 4: Suppose two edges that do not bound the same regions, both of which
connect to a degree 5 vertex, are connected to the new vertex. This case is
equivalent to Case 3, except the new vertex and vertex 7 are switched - the
graphs are isomorphic. Therefore, this graph will also be projective planar.

From these four cases, we can conclude that no splitting of a degree 4 vertex
will create a minor-minimal IPL graph with 16 edges. Now we must consider the
vertices of degree 5. They are all equivalent, so without loss of generality,
we have chosen vertex 2. Assign numbers to its adjacent edges: Edge 1 connects
vertex 2 to vertex 1, Edge 2 connects vertex 2 to vertex 4, Edge 3 connects
vertex 2 to vertex 6, Edge 4 connects vertex 2 to vertex 3, and Edge 5
connects vertex 2 to vertex 7.

Figure 32: Graph $P_{7}$ with the edges incident to vertex 2 labelled.

Case 1: Suppose four of the five edges connect to the new vertex. This will
create a homeomorphic graph, so this case will create a projective planar
graph.

Case 2: Suppose two edges that bound the same region connect to the new
vertex. This case will create a projective planar graph, as seen in Figure 34.

Case 3: Suppose two edges that bound the same region remain connected to the
old vertex, and the remaining three edges connect to the new vertex. This case
is equivalent to Case 2, except the new vertex and vertex 2 are switched - the
graphs are isomorphic. This means that this case will also create a projective
planar graph.

Case 4: Suppose the two edges that connect to the degree 5 vertices are
connect to the new vertex. This means edges 1 and 4 connect to the new vertex.
This graph is nonprojective planar, as seen in Figure 34, but it is not minor-
minimally IPL, as this graph has $K_{4,4}-e$ as a subgraph. The minor
$K_{4,4}-e$ is formed by deleting the edge that connects 1 and 3.

Figure 33: Case 2 Embedding

Figure 34: Case 4 Embedding

The graph in Figure 34 is equivalent to Graph (D) from the image in the
introduction. The graphs are isomorphic, as they are the same graph when the
vertices are labelled like this:

Figure 35: Equivalent embedding to Graph (D)

Case 5: Suppose the three edges that connect to degree 4 vertices are
connected to the new vertex. This case is equivalent to Case 4, except the new
vertex and vertex 2 are switched - the graphs are isomorphic. This means this
graph is also IPL, but not minor-minimally.

Case 6: Suppose two edges that do not bound the same region, one of which
connects to a degree 4 vertex and the other connects to a degree 5 vertex, are
connected to the new vertex. Without loss of generality, we have chosen edges
1 and 3. This first embedding is not projective planar, as seen in Figure 37.
However, there is another embedding that is projective planar, as seen in
Figure 37, so this case does not create an IPL graph.

Figure 36: Case 6 Embedding 1

Figure 37: Case 6 Embedding 2

Case 7: Suppose two edges that do not bound the same region, one of which
connects to a degree 4 vertex and the other connects to a degree 5 vertex,
remain connected to vertex 2 and the remaining three edges are connected to
the new vertex. This case is equivalent to Case 6, except the new vertex and
vertex 2 are switched - the graphs are isomorphic. This means that this case
will also create a projective planar graph.

Case 8: Suppose two edges that connect to the degree 5 vertices and do not
bound the same region are connected to the new vertex. Without loss of
generality, we have chosen edges 2 and 5 to connect to the new vertex. This
first embedding is not projective planar, as seen in Figure 39. However, there
is another embedding that is projective planar, as seen in Figure 39, so this
case does not create an IPL graph.

Figure 38: Case 8 Embedding 1

Figure 39: Case 8 Embedding 2

From these cases, we can conclude that no splitting of a degree 5 vertex will
create a minor-minimal IPL graph with 16 edges. Thus, we can conclude none of
graphs that contain $P_{7}$ as a minor with 16 edges that result from vertex
splittings are minor-minimally IPL.

Now, consider graph $K_{3,3,1}$(C). $K_{3,3,1}$ has six vertices of degree 4
and one vertex of degree 6. The six vertices of degree 4 are all equivalent,
so without loss of generality, we have chosen vertex 1. Assign numbers to its
adjacent edges: edge 1 connects vertex 1 to vertex 2, edge 2 connects vertex 1
to vertex 7, edge 3 connects vertex 1 to vertex 6, and edge 4 connects vertex
1 to vertex 4.

Figure 40: Graph $K_{3,3,1}$ with the edges incident to vertex 1 labelled.

Case 1: Suppose three of the four edges connect to the new vertex. This will
create a homeomorphic graph, so this case will create a projective planar
graph.

Case 2: Suppose two edges that bound the same region connect to the new
vertex. This case will create a projective planar graph, as seen in Figure 43.

Case 3: Suppose two edges that do not bound the same regions, one of which
connects to a degree 6 vertex, are connected to the new vertex. This first
embedding is not projective planar, as seen in Figure 43. However, there is
another embedding that is projective planar, as seen in Figure 43, so this
case does not create an IPL graph.

Figure 41: Case 2 Embedding

Figure 42: Case 3 Embedding 1

Figure 43: Case 3 Embedding 2

Case 4: Suppose two edges that do not bound the same regions, both of which
connect to degree 4 vertices, are connected to the new vertex. This case is
equivalent to Case 3, except the new vertex and vertex 1 are switched - the
graphs are isomorphic. Therefore, this graph will also create a projective
planar graph.

We can conclude that no splitting of a degree 4 vertex of $K_{3,3,1}$ will
create a minor-minimal IPL graph with 16 edges.

Next, we will examine the degree 6 vertex, vertex 7. Assign numbers to its
adjacent edges: edge 1 connects vertex 7 to vertex 1, edge 2 connects vertex 7
to vertex 2, edge 3 connects vertex 7 to vertex 3, edge 4 connects vertex 7 to
vertex 4, edge 5 connects vertex 7 to vertex 5, and edge 6 connects vertex 7
to vertex 6.

Figure 44: Graph $K_{3,3,1}$ with the edges incident to vertex 7 labelled.

Case 1: Suppose five of the six edges connect to the new vertex. This will
create a homeomorphic graph, so this case will create a projective planar
graph.

Case 2: Suppose two edges that bound the same region connect to the new
vertex. This case will create a projective planar graph, as seen in Figure 47.

Case 3: Suppose two edges that bound the same region remain connected to the
old vertex, and the remaining four edges connect to the new vertex. This case
is equivalent to Case 2, except the new vertex and vertex 7 are switched - the
graphs are isomorphic. This means that this case will also create a projective
planar graph.

Case 4: Suppose three edges that bound adjacent regions connect to the new
vertex. This case will create a projective planar graph, as seen in Figure 47.

Figure 45: Case 2 Embedding

Figure 46: Case 4 Embedding

Figure 47: Case 5 Embedding

Case 5: Suppose two edges that are not adjacent, separated by one edge between
their regions, connect to the new vertex. Without loss of generality, chose
edges 1 and 3. This embedding is not projective planar, as seen in Figure 47,
but it is not minor-minimally IPL, because it has $K_{4,4}-e$ as a minor.
Delete the edge that connects vertices 5 and 7 to get $K_{4,4}-e$.

Case 6: Suppose two edges that are not adjacent, separated by one edge between
their regions, remain connected to vertex 7 and the remaining edges connect to
the new vertex. Without loss of generality, chose edges 2, 4, 5, and 6 to
connect to the new vertex. This case is equivalent to Case 5, except the new
vertex and vertex 7 are switched - the graphs are isomorphic. This means that
the graph is IPL, but not minor-minimally.

Case 7: Suppose two edges that are not adjacent, separated by two edges
between their regions, connect to the new vertex. Without loss of generality,
we have chosen edges 1 and 4. This first embedding is not projective planar,
as seen in Figure 49. However, there is another embedding that is projective
planar, as seen in Figure 49, so this case does not create an IPL graph.

Figure 48: Case 7 Embedding 1

Figure 49: Case 7 Embedding 2

Case 8: Suppose two edges that are not adjacent, separated by two edges
between their regions, remain connected to vertex 7 and the remaining edges
connect to the new vertex. Without loss of generality, we have chosen edges 2,
3, 5, and 6 to connect to the new vertex. This case is equivalent to Case 7,
except the new vertex and vertex 7 are switched - the graphs are isomorphic.
Therefore, this case will also create a projective planar graph.

Case 9: Suppose two edges that bound the same region and a third edge that is
the opposite of either of those two edges connect to the new vertex. Without
loss of generality, we have chosen edges 1, 2, and 4 to connect to the new
vertex. This first embedding is not projective planar, as seen in Figure 51.
However, there is another embedding that is projective planar, as seen in
Figure 51, so this case does not create an IPL graph.

Figure 50: Case 9 Embedding 1

Figure 51: Case 9 Embedding 2

Case 10: Suppose three edges, where no two edges bound the same region,
connect to the new vertex. Without loss of generality, we have chosen edges 1,
3, and 5 connect to the new vertex. This embedding is not projective planar,
as seen in Figure 52. It is the graph $K_{4,4}$. Thus, it is not a new minor-
minimally IPL, as $K_{4,4}-e$ is a minor.

Figure 52: Case 10, which is $K_{4,4}$

We can conclude that no splitting of the degree 7 vertex of $K_{3,3,1}$ will
create a minor-minimal IPL graph with 16 edges. Thus, we can conclude none of
the graphs containing $K_{3,3,1}$ as a minor on 16 edges that result from
vertex splittings are minor-minimally IPL.

Now, consider graph $P_{8}$(E). This graph has three vertices of degree 3,
four vertices of degree 4, and one vertex of degree 5. First, we consider the
degree 4 vertices. They are all equivalent, so without loss of generality, we
have chosen vertex 3. Assign numbers to its adjacent edges: edge 1 connects
vertex 3 to vertex 7, edge 2 connects vertex 3 to vertex 4, edge 3 connects
vertex 3 to vertex 8, and edge 4 connects vertex 3 to vertex 2.

Figure 53: Graph $P_{8}$ with the edges incident to vertex 3 labelled.

Case 1: Suppose three of the four edges connect to the new vertex. This will
create a homeomorphic graph, so this case will create a projective planar
graph.

Case 2: Suppose two edges that bound the same region connect to the new
vertex. This case will create a projective planar graph, as seen in Figure 56.

Case 3: Suppose opposite vertices, each from a degree 4 vertex, connect to the
new vertex. For this example, edges 2 and 4 connect to the new vertex. This
first embedding is not projective planar, as seen in Figure 56. However, there
is another embedding that is projective planar, as seen in Figure 56, so this
case does not create an IPL graph.

Figure 54: Case 2 Embedding

Figure 55: Case 3 Embedding 1

Figure 56: Case 3 Embedding 2

Case 4: Suppose opposite vertices, one from a degree 3 vertex and one from a
degree 5 vertex, connect to the new vertex. For this example, this would mean
edges 1 and 3 connect to the new vertex. This case is equivalent to Case 3,
except the new vertex and vertex 3 are switched - the graphs are isomorphic.
Therefore, this graph will also be projective planar.

We can conclude that no splitting of the degree 4 vertices of $P_{8}$ will
create a minor-minimal IPL graph with 16 edges. Next we will look at the
vertex of degree 5, vertex 8. Assign numbers to its adjacent edges: Edge 1
connects vertex 8 to vertex 4, Edge 2 connects vertex 8 to vertex 6, Edge 3
connects vertex 8 to vertex 1, Edge 4 connects vertex 8 to vertex 2, and Edge
5 connects vertex 8 to vertex 3.

Figure 57: Graph $P_{8}$ with the edges incident to vertex 8 labelled.

Case 1: Suppose four of the five edges connect to the new vertex. This will
create a homeomorphic graph, so this case will create a projective planar
graph.

Case 2: Suppose two edges that bound the same region connect to the new
vertex. This case will create a projective planar graph, as seen in Figure 60.

Case 3: Suppose two edges that bound the same region remain connected to the
old vertex, and the remaining three edges connect to the new vertex. This case
is equivalent to Case 2, except the new vertex and vertex 8 are switched - the
graphs are isomorphic. This means that this case will also create a projective
planar graph.

Case 4: Suppose the two opposite edges that connect to degree 4 vertices
connect to the new vertex. This means edges 1 and 3 connect to the new vertex.
This first embedding is not projective planar, as seen in Figure 60. However,
there is another embedding that is projective planar, as seen in Figure 60, so
this case does not create an IPL graph.

Figure 58: Case 2 Embedding

Figure 59: Case 4 Embedding 1

Figure 60: Case 4 Embedding 2

Case 5: Suppose the two opposite edges that connect to degree 4 vertices
remain connected to vertex 8, and the remaining edges connect to the new
vertex. This means edges 2, 4, and 5 connect to the new vertex. This case is
equivalent to Case 4, except the new vertex and vertex 8 are switched - the
graphs are isomorphic. This means this case also creates a projective planar
graph.

Case 6: Suppose two edges that are not opposites and that connect to degree 4
vertices connect to the new vertex. Without loss of generality, we have chosen
edges 1 and 4. This first embedding is not projective planar, as seen in
Figure 62. However, there is another embedding that is projective planar, as
seen in Figure 62, so this case does not create an IPL graph.

Figure 61: Case 6 Embedding 1

Figure 62: Case 6 Embedding 2

Case 7: Suppose two edges that are not opposites and that connect to degree 4
vertices remain connected to vertex 8 and the remaining 3 edges are connected
to the new vertex. This case is equivalent to Case 6, except the new vertex
and vertex 8 are switched - the graphs are isomorphic. This means that this
case will also create a projective planar graph.

Case 8: Suppose two edges that do not bound the same region, one from a degree
3 vertex and one from a degree 4 vertex, are connected to the new vertex.
Without loss of generality, we have chosen edges 2 and 4 to connect to the new
vertex. This first embedding is not projective planar, as seen in Figure 64.
However, there is another embedding that is projective planar, as seen in
Figure 64, so this case does not create an IPL graph.

Figure 63: Case 8 Embedding 1

Figure 64: Case 8 Embedding 2

From these cases, we can conclude that no splitting of the degree 5 vertex
will create a minor-minimal IPL graph with 16 edges. Thus, we can conclude
none of the graphs containing $P_{8}$ as a minor on 16 edges that result from
vertex splittings are minor-minimally IPL.

Now, consider graph $P_{9}$(F). This graph has six vertices of degree 3 and
three vertices of degree 4. We only have to consider the degree 4 vertices.
They are all equivalent, so without loss of generality, we have chosen vertex
5. Assign numbers to its adjacent edges: edge 1 connects vertex 5 to vertex 4,
edge 2 connects vertex 5 to vertex 8, edge 3 connects vertex 5 to vertex 6,
and edge 4 connects vertex 5 to vertex 2.

Figure 65: Graph $P_{9}$ with the edges incident to vertex 5 labelled.

Case 1: Suppose three of the four edges connect to the new vertex. This will
create a homeomorphic graph, so this case will create a projective planar
graph.

Case 2: Suppose two edges that bound the same region connect to the new
vertex. This case will create a projective planar graph, as seen in Figure 68.

Case 3: Suppose opposite vertices, each from a degree 4 vertex, connect to the
new vertex. For this example, this would mean edges 1 and 3 connect to the new
vertex. This first embedding is not projective planar, as seen in Figure 68.
However, there is another embedding that is projective planar, as seen in
Figure 68, so this case does not create an IPL graph.

Figure 66: Case 2 Embedding

Figure 67: Case 3 Embedding 1

Figure 68: Case 3 Embedding 2

Case 4: Suppose opposite vertices, each from a degree 3 vertex, connect to the
new vertex. For this example, this would mean edges 2 and 4 connect to the new
vertex. This case is equivalent to Case 3, except the new vertex and vertex 5
are switched - the graphs are isomorphic. Therefore, this graph will also be
projective planar.

We can conclude that no splitting of the degree 4 vertices of $P_{9}$ will
create a minor-minimal IPL graph with 16 edges. Thus, we can conclude none of
the graphs containing $P_{9}$ as a minor on 16 edges that result from vertex
splittings are minor-minimally IPL.

Finally, consider graph $P_{10}$(G). For $P_{10}$, every vertex has degree 3.
Every vertex splitting will be projective planar because it will be
homeomorphic to the original graph. Thus, we can conclude none of the graphs
containing $P_{10}$ as a minor on 16 edges that result from vertex splittings
are minor-minimally IPL.

###  3.7 35 minor-minimal nonprojective planar graphs

Only one of the 35 minor-minimal nonprojective-planar graphs is IPL, and it is
$K_{4.4}-e$. A direction for future research would be to examine those graphs
plus $K_{1}$. We conjecture that the resulting graphs would all be IPL.

##  4 Acknowledgements

This material is based upon work obtained by the research group at the 2021
Reserach Experience for Undergraduates Program at SUNY Potsdam and Clarkson
University, advised by Joel Foisy and supported by the National Science
Foundation under Grant No. H98230-21-1-0336; St. Catharine’s College,
University of Cambridge; and Universidad Autónoma del Estado de Hidalgo. We
would like to thank Jeffrey Dinitz for Archdeacon’s list of minor-minimal
nonouter-projective-planar graphs.

## References

  * [1] Archdeacon, D.; Hartsfield, N.; Little, C.H.H.; Mohar, B., Obstruction sets for outer-projective-planar graphs. Ars Combinitoria. 49 (1998), 113-127.
  * [2] Bustamante, J.; Federman, J.; Foisy, J.; Kozai, K.; Matthews, K.; McNamara, K.; Stark, E.; Trickey, K., Intrinsically linked graphs in projective space. Algebraic $\&$ Geometric Topology, Mathematical Sciences Publishers (2009), 1255-1274.
  * [3] Dehkordi, H.; Farr, G., Nonseparating planar graphs. The Electronic Journal of Combinatorics. 28 No. 1, Jan 2021.
  * [4] Duong, Y.; Foisy, J.; Meehan, K.; Merrill, L.; Snyder, L., Intrinsically linked signed graphs in projective space. Discrete Mathematics 312 (2012), 67-85.
  * [5] Foisy, J.; Knowles, E.; Nolasco Hernandez, U; Shen, Y; Topete Galván, L; Wickham, L., Links in projective planar graphs, arXiv:2206.05758.
  * [6] Glover, H.; Huneke, J.; San Wang, C., 103 Graphs that are irreducible for the projective plane. Journal of Combinatorial Theory, Series B 27 (1979), 332-370.
  * [7] Kawarabayashi, K.; Kreutzer, S.; Mohar, B., Linkless and flat embeddings in 3-space and the unknot problem. Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, ACM, (2010), 97–106.
  * [8] Robertson, N., Seymour, P.D., and Thomas R., Linkless embeddings of graphs in 3-space. Bull. Amer. Math. Soc. (N.S.) 28, no. 1, (1993), 84–89