Strong $3$-Flow Conjecture for Projective Planar Graphs

We define an orientation of a graph $G$ to be the directed graph $D$ obtained by adding a direction to each edge. With reference to determining the $\mathbb{Z}_{3}$-connectivity of $G$ with prescription function $p:V\rightarrow\{-1,0,1\}$, an orientation is valid if for each vertex $v\in V(G)$,

It can be easily seen that this is equivalent to a $\mathbb{Z}_{3}$-flow.

A vertex $d$ in a graph $G$ is a directed vertex if all its incident edges are directed. We call this an orientation of $d$. We say that an orientation of $G$ extends the orientation of $d$ if the direction of the edges at $d$ is maintained. In cases involving a directed vertex we take the term valid orientation to include that the orientation extends that of $d$.

We lift a pair of edges $uv$ and $vw$ in a graph $G$ by deleting $uv$ and $vw$, and adding an edge $vw$. We define an edge-cut $\delta(A)$ in $G$ to be internal if either $A$ or $G-A$ does not intersect the boundary of the specified face(s) of $G$.

First, we consider the idea of a specified face. Theorem 1.3 allows vertices of degree less than $5$ on the boundary of the outer face. However, a graph embedded in a higher genus surface does not have a defined outer face, so the result cannot be directly extended.

Let $G$ be a graph with a specified face $F_{G}$. Let $G^{\prime}$ be a graph obtained from $G$ by one or more operations. Unless otherwise stated, the specified face $F_{G^{\prime}}$ is defined as follows:

1. 1.

   Suppose that $G^{\prime}$ is obtained from $G$ by deleting or contracting a connected subgraph of $G$ that has no edge in common with the boundary of $F_{G}$. Then $F_{G^{\prime}}=F_{G}$.

2. 2.

   Suppose that $G^{\prime}$ is obtained from $G$ by contracting a connected subgraph of $G$ that contains the boundary of $F_{G}$. Then $G^{\prime}$ has no specified face. A face can be chosen arbitrarily; in general we will chose a specified face incident with the vertex of contraction.

3. 3.

   Suppose that $G^{\prime}$ is obtained from $G$ by deleting an edge $e$ in the boundary of $F_{G}$. Let $F$ be the other face incident with $e$. Then $F_{G^{\prime}}$ is the face formed by the union of the boundaries of $F$ and $F_{G}$ (without $e$).

4. 4.

   Suppose that $G^{\prime}$ is obtained from $G$ by deleting a vertex $v$ in the boundary of $F_{G}$. Let $F_{1}$, $F_{2}$,…,$F_{k}$ be the other faces incident with $v$. Then $F_{G^{\prime}}$ is the face formed by the union of the boundaries of $F_{1}$, $F_{2}$,…,$F_{k}$, and $F_{G}$ (without the edges incident with $v$).

5. 5.

   Suppose that $G^{\prime}$ is obtained from $G$ by contracting a connected subgraph $H$ of $G$ whose intersection with $F_{G}$ is a path $P$ of length at least one. Then $F_{G^{\prime}}$ is the face formed by the boundary of $F_{G}$ without $P$. If the intersection of $H$ with $F_{G}$ consists of more than one path, this contraction can simply be completed in multiple steps.

6. 6.

   Suppose that $G^{\prime}$ is obtained from $G$ by lifting a pair of adjacent edges $e_{1}$, $e_{2}$, where $e_{1}$ is in the boundary of $F_{G}$, $e_{2}$ is not, and $e_{1}$ and $e_{2}$ are consecutive at their common vertex. Let $F_{1}$ be the other face incident with $e_{1}$. Note that $F_{1}$ is incident with $e_{2}$. Let $F_{2}$ be the other face incident with $e_{2}$. Then $F_{G^{\prime}}$ is the face formed by the union of the boundaries of $F_{G}$ and $F_{2}$ (using the lifted edge instead of $e_{1}$ and $e_{2}$).

When performing these operations we will not explicitly state the new specified face unless necessary.

As in Richter et al., [10], throughout this paper we are working with graphs for which all vertices not on the boundary of the specified face(s) have at least $5$ edge-disjoint paths to the boundary of the specified face(s). We describe here how reductions to the graph affect this condition. The proof of this result is straightforward, and can be found in [2].

We therefore only discuss the preservation of this property in cases where Lemma 2.1 does not apply.

Let $G$ be a graph with a directed vertex $d$. An edge-cut $\delta(A)$ in $G$ with $d\in A$ is $k$-robust if $|A|\geq 2$ and $|G-A|\geq k$.

Throughout this paper we will perform local reductions on graphs. Many of these reductions will involve considering $2$-robust edge-cuts, either because $G$ has a small edge-cut that must be reduced, or because we must verify that the graph resulting from a reduction does not have any small edge-cuts. In all cases, we first consider the smallest possible edge-cuts. Thus, if we consider a $2$-robust $k$-edge-cut $\delta(A)$ in a graph $G$, we may assume that $G$ has no $2$-robust at most $(k-1)$-edge-cut. Thus it may be assumed that either $G[A]$ is connected, or it consists of two isolated vertices whose degrees sum to $|\delta(A)|$. The same is true of $G-A$. Given the sizes of the cuts we consider, generally both $G[A]$ and $G-A$ will be connected.

Let $\delta(A)$ and $\delta(B)$ be distinct edge-cuts in $G$. We say that $\delta(A)$ and $\delta(B)$ cross if $A\cap B$, $A\setminus B$, $B\setminus A$, and $\overline{A\cup B}$ are all non-empty. Throughout this paper we consider graphs that are allowed to have non-crossing $2$-robust $3$-edge-cuts under certain restrictions. The following well-known result allows us to assume that such cuts are non-crossing. A proof can be found in [2].

Let $G$ be a graph embedded in the plane, and let $F_{G}$ be a specified face of $G$. If $G$ does not contain a cut vertex, then we may assume that $F_{G}$ is bounded by a cycle. If $G$ is embedded in the projective plane, this is not necessarily true. Suppose that $v$ is a vertex that appears more than once in the boundary walk of $F_{G}$, and assume that $v$ is not a cut vertex. Then there exists a non-contractible curve that passes through only $F_{G}$ and $v$. Cut along this curve, and draw the graph on the plane. The result is a planar graph with one specified face containing two copies of $v$. See Figure 1 for an illustration. Contract the two copies of $v$ to a single vertex. Then $G$ is a planar graph with two specified faces, each containing $v$. The following result of de Jong, 2020b [3] guarantees that such a graph has a valid orientation.

Let $G$ be a graph embedded in the plane and let $F_{G}$ be a specified face of $G$. Suppose that $F_{G}$ has a chord $e$ with endpoints $u$ and $v$. Then there exist subgraphs $H$ and $K$ of $G$ such that $H\cap K=\{\{u,v\},\{e\}\}$ and $H\cup K=G$. This is a property that Richter et al., [10] exploited when proving the Strong $3$-Flow Conjecture for planar graphs, and a property that we use throughout this paper.

Now suppose that $G$ is a graph embedded in the projective plane with a cycle $C$ bounding a closed disk. Let $e$ be a chord of $C$. If $C+e$ is contained in an open disk, then $e$ is a contractible chord. Otherwise it is a non-contractible chord. This is relevant in the case where the specified face $F_{G}$ is bounded by a cycle. If $F_{G}$ has a contractible chord, we may use techniques analogous to those in the plane to reduce the graph. In the case of a non-contractible chord, the graph is not split into subgraphs as it is in the plane, and we require different techniques. We see here that the deletion of such a chord and its endpoints results in a planar graph.

In practice, we will obtain graphs with up to three vertices of degree three. The following result of de Jong, 2020b [3] shows that such graphs have a valid orientation.

In the proof of the Strong $3$-Flow Conjecture for graphs in the projective plane, two specific classes of graphs will arise. Let $i$ be an odd integer greater than or equal to $5$, and define $B_{i}$ to be the circulant graph on $i$ vertices with jumps $1$ and $\frac{i-1}{2}$. Label the vertices $v_{1},v_{2},...,v_{i}$. Let $A_{i}$ be the graph on $i+1$ vertices obtained from $B_{i}$ by subdividing $v_{1}v_{i}$ with a vertex $v_{0}$, and adding an edge $v_{0}v_{\frac{i+1}{2}}$. We show that both classes of graphs satisfy the Strong $3$-Flow Conjecture.