About $k$-ring in planar graph

Question

I am a student currently doing some research on the Four Color Theorem. I mainly studied the paper Efficiently Four-coloring Planar Graphs. In this paper, the authors define $k$-ring as follows:

A $k$-ring is a cycle on $k$ edges with at least $1$ vertex in each of its interior and exterior.

Then, they have some results related to $k$-rings that I cannot see how they get, which I will list below. Answering any one of my problems is welcomed.

1. In the paper (P.6, Algorithm 1, paragraph 4), the authors stated that

If $G$ has a vertex $x$ of degree $k\leq 4$, then the circuit $C$ surrounding it is a $k$-ring.

For the above result, if we consider the following graph, the orange vertex is of degree $4$, but I cannot find any $4$-ring in the graph. So I would like to know how should I understand the above result.

2. In the same paper (P.5, paragraph 3), the authors stated that

It turns out that every configuration $K$ of $U$ has diameter at most four; i.e. that each pair of vertices of $G(K)$ have distance at most four in $G(K)$. Using this bound on the diameter, it is easily seen that if $K$ is weakly, but not strongly contained in $G$, then $G$ has a $k$-ring for $k\leq 4$ or a non-trivial $5$-ring.

However, I found that the result is not that ''easy'', as I cannot make any progress on proving this even after hours of thinking. So any insight or proof provided will be very appreciated.

Answer 1

Regarding the first question: this is a bit of imprecision in the paper. At this point, we know that the graph is a triangulation, so if $v$ is any vertex, there is a cycle through all its neighbors. If $\deg(v) = k$, this cycle is almost guaranteed to be a $k$-ring: there is exactly one vertex ($v$ itself) on one side, and $n-k-1$ vertices on the other. However, if $n = k+1$, then there are no vertices on the other side of the cycle, which is what we see here.

We are considering $k \le 4$, so this is only going to come up for $5$-vertex graphs. You can treat this graph as a special case if you like, or you can make use of the $3$-ring surrounding the vertex of degree $3$, instead.

---

Regarding the second question, I do not have the whole idea, because I get the sense that some properties of configurations are left out or taken for granted in this paper. However, if $K$ is contained weakly but not strongly, then we get an unexpected short cycle when:

• two distinct $v,w \in V(G(K))$ have $f(v)=f(w)$: then the image of the $v-w$ path in $G(K)$ is a cycle in $G$.
• two non-adjacent $v,w \in V(G(K))$ have $f(v)$ adjacent to $f(w)$: then the image of the $v-w$ path in $G(K)$ together with the edge $f(w)f(v)$ is a cycle in $G$.

The diameter condition guarantees that this cycle has length at most $5$ in both cases; only the second case can result in a cycle of length $5$. It seems plausible that the cycle always ends up containing a vertex of $G$ on both sides (two on both sides in the case of length $5$).