Strong 3-Flow Conjecture for Projective Planar Graphs

NEW

Problem: Reconstructed conjecture: Theorem 3.2 of de Jong–Richter remains true if a PT graph is allowed to have both specified boundary vertices $t$ and $d$, where $t$ is unoriented of degree $3$, $d$ is a preoriented vertex of degree $3$, the prescribed function $p:V(G)\to\mathbb Z_3$ is compatible with the fixed orientation at $d$, and the only allowed $3$-edge-cuts are $\delta(d)$ and $\delta(t)$.

This is the natural meaning of “we may have both $t$ and $d$ in Theorem 3.2, provided $\deg(d)=3$.”

Result: The conjecture is false.

Let

and let $G=K_5-dt$. Thus $a,b,c$ form a triangle, and each of $d,t$ is adjacent to each of $a,b,c$. Embed $G$ in the projective plane using the standard projective-plane embedding of $K_5$ with a pentagonal face bounded by

then delete the chord $dt$. Hence all vertices lie on the boundary of the specified face.

The graph is $3$-edge-connected. Its only $3$-edge-cuts are $\delta(d)$ and $\delta(t)$: indeed, for any cut $S$, compared with $K_5$ the cut size is $|S|(5-|S|)$, except that one subtracts $1$ exactly when $d$ and $t$ are separated. A direct check gives cut size $3$ only for $S=\{d\}$ or $S=\{t\}$, up to complement.

Fix the orientation of the three edges incident with $d$ as

Let the prescription be

Then $\sum_v p(v)=-3\equiv 0\pmod 3$, and the prescription is compatible with the fixed orientation at $d$, since $d$ has three incoming edges.

Suppose a valid orientation extending the fixed orientation exists. Since $t$ has degree $3$ and $p(t)=0$, the three edges incident with $t$ are either all directed into $t$, or all directed out of $t$.

If $a,b,c\to t$, then at each of $a,b,c$ the two edges to $d$ and $t$ are outgoing, contributing $-2\equiv 1$. To achieve prescription $-1$, the two triangle edges at that vertex must both be outgoing. That is impossible on the triangle $abc$.

If $t\to a,b,c$, then at each of $a,b,c$ one edge is outgoing to $d$ and one incoming from $t$, contributing $0$. To achieve prescription $-1$, both triangle edges at that vertex must be incoming. That is also impossible on the triangle.

Thus no valid orientation exists. This refutes the conjecture, even with the natural compatibility condition at $d$.

Citation: No known literature resolution is being used. The conjecture is from de Jong and Richter, “Strong $3$-Flow Conjecture for Projective Planar Graphs,” arXiv:2011.00672, Discussion section.