\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{cite}

\def\udcs{519.172.2} %Here the author places classificators of the paper according to Russian classification system
\def\mscs{05C75} %Here the author places  classificators according to the AMS classification list.
\setcounter{page}{1}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{cor}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{prob}{Problem}
\newtheorem{rem}{Remark}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\top
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]  %Headings in Russian
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 20, стр. ??--?? (2024) \hspace{65mm}{\rm\small УДК \udcs}} %Volume, pages in Russian,
                                                                                    %filled by Editorial board
     \newline
         \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\proofname}{Proof.}
\thispagestyle{empty}

\title{Describing edges in normal plane maps having no adjacent 3-faces}
\author{{O.V.\,Borodin, A.O.\,Ivanova}}%
\address{Oleg Veniaminovich Borodin
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{brdnoleg@math.nsc.ru}%
\address{Anna Olegovna Ivanova
\newline\hphantom{iii} Ammosov North-Eastern Federal
University,
\newline\hphantom{iii} st. Kulakovskogo, 48,
\newline\hphantom{iii} 677013, Yakutsk, Russia}%
\email{shmgnanna@mail.ru}%

\thanks{\sc Borodin, O.V., Ivanova, A.O.
Describing edges in normal plane maps having no adjacent 3-faces}
\thanks{\copyright \ 2024 Borodin O.V., Ivanova A.O}
\thanks{\rm The first author' work was supported by the
Ministry of Science and Higher Education of the Russian Federation
(project no. FWNF-2022-0017). The second author's work was
supported by the Ministry of Science and Higher Education of the
Russian Federation (Grant No. FSRG-2023-0025).}
\thanks{\it Received November, ??, 2023, published  ???, ???,  ????.}%



\top \vspace{1cm} \maketitle {\small
\begin{quote}
\noindent{\sc Abstract. } The weight $w(e)$ of an edge $e$ in a
normal plane map (NPM) is the degree-sum of its end-vertices. An
edge $e=uv$ is an $(i,j)$-edge if $d(u)\le i$ and $d(v)\le j$. In
1940, Lebesgue proved that every NPM has  a $(3,11)$-edge, or
$(4,7)$-edge, or $(5,6)$-edge, where 7 and 6 are best possible. In
1955, Kotzig proved that every 3-polytope has an edge $e$ with
$w(e)\le13$, which bound is sharp. Borodin (1987), answering
Erd\H{o}s' question, proved that every NPM has such an edge.
Moreover, Borodin (1991) refined this by proving that there is
either a $(3,10)$-edge, or $(4,7)$-edge, or $(5,6)$-edge.

Given an NPM, we observe some upper bounds on the minimum weight
of all its edges, denoted by $w$, of those incident with a 3-face,
$w^*$, and those incident with two 3-faces,  $w^{**}$. In
particular, Borodin (1996)  proved that if  $w^{**}=\infty$, that
is if an NPM has no edges incident with two 3-faces, then either
$w^*\le9$ or $w\le8$, where both bounds are sharp.

The purpose of our note is to refine this result by proving that
in fact  $w^{**}=\infty$ implies either a $(3,6)$- or $(4,4)$-edge
incident with a 3-face, or a $(3,5)$-edge, which description is
tight.
\medskip

\noindent{\bf Keywords:} planar graph, plane map, structure
properties, 3-polytope, weight.

 \end{quote}
}


\section{ Introduction}

A normal plane map (NPM) is a plane pseudograph in which loops and
multiple edges are allowed, but the degree of each vertex and face
is at least three. 3-polytopes are in 1--1 correspondence with
3-connected plane graphs, as proved by Wernicke~\cite{We04} back
in 1904.


The degree of a vertex or a face $x$, that is the number of edges
incident with $x$ (loops and cut-edges are counted twice in the
degree of vertex and face, respectively) is denoted by $d(x)$. A
{\em $k$-vertex} is a vertex $v$ with $d(v) = k$. A {\em $k$-face}
$f$ satisfies $d(f) = k$. By $k^+$ or $k^-$ we denote any integer
not smaller or not greater than $k$, respectively. Hence,  a
$k^+$-vertex $v$ satisfies $d(v)\ge k$, etc.

An edge $uv$ is an {\em $(i,j)$-edge} if $d(u)\le i$ and $d(v)\le
j$. The {\it weight} $w(e)$ of an edge $e$ in an NPM is the
degree-sum of its end-vertices. By $\delta(G)$ and $w(G)$ we
denote the minimum vertex degree and the minimum weight of edges
of a graph $G$, respectively. We will drop the argument when it is
clear from context.

Already in 1904, Wernicke~\cite{We04} proved that every NPM  with
$\delta=5$ satisfies $w\le11$. In 1940, Lebesgue~\cite{Le40}
proved that every NPM has  a $(3,11)$-edge, or $(4,7)$-edge, or
$(5,6)$-edge, where 7 and 6 are best possible. In 1955,
Kotzig~\cite{Kg55} proved that every 3-polytope satisfies
$w\le13$, which bound is sharp.

In 1972, Erd\H {o}s (see~\cite{Gr76}) conjectured that Kotzig's
bound $w\le13$ holds for all planar graphs with $\delta\ge3$. The
first  proof of Erd\H {o}s' conjecture is due to
Borodin~\cite{B87}, and is, moreover, given for all NPMs.
Borodin~\cite{B93a,B93b} refined this result by proving that every
NPM  contains a  $(3,10)$-,  or $(4,7)$-, or $(5,6)$-edge (as easy
corollaries of some stronger structural facts having applications
to coloring of plane graphs).


In some coloring applications, it is  important to find a light
edge incident with one or two $3$-faces. Given an NPM, the minimum
weight of all its edges is denoted by $w$, of those incident with
a 3-face, by $w^*$, and those incident with two 3-faces, by
$w^{**}$.

Borodin~\cite{B91} proved that any NPM has either $w^{**}\le 13$,
or $w^*\le10$ or else $w\le8$, where all bounds are best possible.
Some other related results, as well as conjectures and references
can be found in surveys Borodin, Ivanova~\cite{B13}, Jendrol',
Voss~\cite{JV13}) and papers~\cite{ABI16, BBIKN17, B87, B89a, B91,
B93a, B93b,B96a, B96d, B13, BGR10, BI14e, BI16h, BI19c, BIKS07,
BKW97, FM10, Gr76, JM15, JV13, Kg55, Le40, We04}).

In particular, in results on the entire coloring we often deal
with NPMs having $w^{**}=\infty$. In Borodin~\cite{B96a}, it is
proved that such NPMs satisfy the sharp bound $w\le9$, which was
strengthened in Borodin~\cite{B96d} to either $w^*\le9$ or
$w\le8$, where both bounds are sharp.

The purpose of this note is to refine the latter result as
follows.

\begin{theorem}\label{main}
Every normal plane map without adjacent $3$-faces has either a
$(3,6)$- or $(4,4)$-edge incident with a $3$-face, or a
$(3,5)$-edge, which description is tight.
\end{theorem}

\section{Proving Theorem~\ref{main}}

In Borodin~\cite{B96d}, there is obtained a plane graph (with
$w^{**}=\infty$, as also assumed throughout the proof below) with
vertices of degree 3 and 6 only, in which every edge is {\em
semi-weak}, that is incident with a 3-face, and joins a
$3^+$-vertex to a 6-vertex. This confirms that the first option in
Theorem~\ref{main} is necessary and best possible.

The second option is due to by the well-known
(3,4,3,4)-Archimedean solid, in which every edge joins two
4-vertices and is incident with a 3-face and 4-face. A simple way
to obtain this construction is to join the middles of all edges of
the cube inside the corresponding faces, followed by deleting the
edges and vertices of the initial cube.

The third option is confirmed by the dual of the $(3,5,3,5)$-Archimedean solid, in which every edge joins a
3-vertex with a 5-vertex and is incident with two 4-faces.

\subsection{Discharging and its consequences}

 By $M$ denote a counterexample to Theorem~\ref{main}.
Let $V$, $E$, and $F$ be the sets of vertices, edges and faces of
$M$, respectively. Euler's formula $|V|-|E|+|F|=2$ for $M$ may be
rewritten as

\begin{equation}
\sum_{x\in V\cup F}(d(x)-4)=-8. \label{eq:euler}
\end{equation}

Every vertex and face $x$ contributes the {\em charge}
$\mu(x)=d(x)-4$ to (\ref{eq:euler}), so only the charges of
$3$-vertices and 3-faces are negative. Using the properties of $M$
as a counterexample, we define a local redistribution of $\mu$'s,
preserving their sum, such that the {\em new charge} $\mu'(x)$ is
non-negative for all $x\in V\cup F$. This will contradict the fact
that the sum of the new charges is, by (\ref{eq:euler}), equal to
$-8$.

\medskip
In what follows, we denote the vertices adjacent to a vertex $v$
in a cyclic order by $v_1,\ldots,v_{d(v)}$. An edge is {\em
strong} if it is not incident with a 3-face.

 \medskip

We apply the following rules of discharging.

 \medskip
{\bf R1.} {\em Every $3$-face receives $\frac13$ from each
incident vertex.}

 \medskip
{\bf R2.} {\em Every $3$-vertex receives $\frac 12$ along each
semi-weak edge from a $7^+$-vertex.}

 \medskip
{\bf R3.} {\em Every $3$-vertex receives $\frac 13$ along each
strong edge from a $6^+$-vertex.}

 \medskip
{\bf R4.} {\em Every $4$-vertex receives $\frac 16$ along each
semi-weak edge from a $5^+$-vertex.}


\subsection{Checking that $\mu'(x)\ge0$ whenever $x\in V\cup F$}

\quad

\quad


{\sl CASE 1.} $f\in F$. If $d(f)=3$ then
$\mu'(f)=3-4+3\times\frac13=0$ by R1.
 If $d(f)\ge4$ then $f$ does not participate in R1--R4, so $\mu'(f)=\mu(f)=d(f)-4\ge0$.

\medskip

{\sl CASE 2.} $v\in V$.

\medskip

{\sl Subcase 2.1.} $d(v)=3$. If $v$ is incident with a $3$-face
$f=v_1vv_2$ (precisely one, since  $w^{**}=\infty$), then $v$
receives $2\times\frac12$ from  the two incident $7^+$-vertices
$v_1,v_2$ by R2 and $\frac13$ from the $6^+$-vertex $v_3$ by R3
due to the absence of $(3,5)$-edge and semi-weak $(3,6)$-edge in
$M$. Also, $v$ gives $\frac13$ to $f$ by R1, so
$\mu'(v)=3-4+2\times\frac12+\frac13-\frac13=0$.

If $v$ is not incident with 3-faces, then $\mu'(v)=3-4+3\times
\frac13=0$ by R3 due to the absence of $(3,5)$-edge in $M$.

\medskip

{\sl Subcase 2.2.} $d(v)=4$. Note that each $3$-face $f=v_1vv_2$
at $v$ results in giving $\frac13$ to $f$ by R1 and receiving
$2\times\frac16$ from  the  incident $5^+$-vertices $v_1,v_2$ by
R4 due to the absence of semi-weak $(4,4)$-edge in $M$, so in fact
$f$ costs nothing to $v$. Therefore,
 $\mu'(v)=0$, no matter whether $v$ is incident with two, one or no 3-faces.

\medskip

{\sl Subcase 2.3.} $d(v)=5$. Now $v$ is incident with at most two
3-faces, and each 3-face $f=v_1vv_2$ receives $\frac13$ from $v$
by R1, while at most one of $v_1,v_2$ is a 4-vertex due to the
absence of semi-weak $(4,4)$-edges in $M$, receiving $\frac16$
from $v$ by R4. So the total expenditure of $v$ caused by $f$ is
at most $\frac12$, which means that $\mu'(v)\ge 5-4-2\times
\frac12=0$.

\medskip

{\sl Subcase 2.4.} $d(v)=6$. Due to the argument in Subcase~2.3
combined with the absence of semi-weak $(3,6)$-edges in $M$, each
3-face at $v$ costs  $v$ at most $\frac13+\frac16$ by R1 and R4.
Let $T$ be the number of 3-faces at $v$; clearly $0\le T\le 3$.
Now it follows from R1, R3 and R4 that $\mu'(v)\ge 6-4 - T\times
\frac12-(6-2T)\times \frac13= \frac T6\ge0$.

\medskip

{\sl Subcase 2.5.} $d(v)\ge7$. Now a 3-face $f=v_1vv_2$ at $v$
collects at most $\frac13+\frac12=\frac56$ from $v$ by R1, R2 and
R4. Since $v$ is incident with at most
$\lfloor\frac{d(v)}2\rfloor$ $3$-faces, we have  $\mu'(v)\ge d(v)-4-T\times\frac56-(d(v)-2T)\times\frac13 = 
\frac{2d(v)}3-4-T\times\frac16 \ge \frac{2d(v)}3-4-\frac{d(v)}2\times\frac16 = \frac{7d(v)-48}{12} >0$, as
desired.

\medskip


Thus we have proved that $\mu'(x)\ge0$ for all $x\in V\cup F$,
which contradicts (1) and thus completes the proof of
Theorem~\ref{main}.




\begin{thebibliography}{1}

\bibitem{ABI16} V.A.~Aksenov, O.V.~Borodin, A.O.~Ivanova, {\it An extension of Kotzig's Theorem},
Discuss. Math. Graph Theory, {\bf 36, 4} (2016) 889--897.

\bibitem{BBIKN17} Ts.Ch-D.~Batueva, O.V.~Borodin, M.A.~Bykov, A.O.~Ivanova,
 O.N.~Kazak, D.V.~Nikiforov, {\it  Refined weight of edges in normal
 plane maps}, Discrete Math., {\bf 340}, 11 (2017) 2659--2664.

\bibitem{B87} O.V.Borodin, {\it Coupled colorings of graphs on a plane (Russian)}, Metody Diskret.
Analiz.,  {\bf 45} (1987), 21--27.

\bibitem{B89a} O.V.Borodin, {\it On the total coloring of planar graphs}, J. Reine Angew. Math.,
{\bf 394} (1989) 180--185.

\bibitem{B91} O.V.Borodin, {\it Joint generalization of the theorems of Lebesgue and Kotzig
on the combinatorics of planar maps (Russian)}, Diskret. Mat.,
{\bf 3, 4} (1991),  24--27.

\bibitem{B93a} O.V.Borodin, {\it Joint extension of two Kotzig's theorems on $3$-polytopes},
Combinatorica, {\bf 13, 1} (1992) 121--125.

\bibitem{B93b} O.V.Borodin,  {\it The structure of neighborhoods of an edge
  in planar graphs and the simultaneous coloring of vertices, edges and faces (Russian)}, Mat. Zametki,
  {\bf 53, 5} (1993) 35--47.

\bibitem{B96a} O.V. Borodin, {\it Structural theorem on plane graphs with application to the entire
    coloring}, J. Graph Theory, {\bf 23, 3} (1996) 233--239.

\bibitem{B96d} O.V. Borodin,  {\it More about the weight of edges in planar graphs},
Tatra Mountains Math. Publ., {\bf 9} (1996) 11--14.

\bibitem{B13}  O.V.Borodin, {\it Colorings of plane graphs: a survey}, Discrete Math.,
{\bf 313, 4} (2013) 517--539.

\bibitem{BGR10} O.V.Borodin, A.N.Glebov, A.Raspaud, {\it Planar graphs without triangles adjacent
 to cycles of length from $4$ to $7$ are $3$-colorable}, Thomassen's special issue of Discrete Math.,
 {\bf 310, 20} (2010) 2584--2594.

\bibitem{BI14e}  O.V.Borodin,  A.O.Ivanova, {\it The vertex-face weight of edges in 3-polytopes  (Russian)},
Sibirsk. Mat. Zh., {\bf 56, 2} (2015) 338--350. (Translation in
Sib. Math. J., {\bf 56, 2} (2015) 275--284).

\bibitem{BI16h} O.V.~Borodin, A.O.~Ivanova, {\it Weight of edges in normal plane maps}, Discrete Math.,
{\bf 339, 5} (2016) 1507--1511.

\bibitem{BI19c} O.V.~Borodin, A.O.~Ivanova, {\it An improvement of Lebesgue's description of edges
in $3$-polytopes and faces in plane quadrangulations}, Discrete
Math., {\bf 342, 6} (2019) 1820--1827.

\bibitem{BIKS07} O.V.Borodin, A.O.Ivanova, A.V.Kostochka, N.N.Sheikh, {\it Minimax degrees of
quasiplane graphs without $4$-faces}, Sib. Elektron. Mat. Izv.,
{\bf 4} (2007) 435--439.

\bibitem{BKW97} O.V. Borodin, A.V.Kostochka, and D.R.Woodall, {\it List edge and list total colourings
of multigraphs},  J. Combin. Theory (B), {\bf 71, 2} (1997)
184--204.

\bibitem{FM10} B.Ferencov\'{a}, T.Madaras, {\it Light graph in families of
polyhedral graphs with prescribed minimum degree, face size, edge
and dual edge weight}, Discrete Math., {\bf 310} (2010)
1661--1675.

\bibitem{Gr76} B.Gr\"{u}nbaum, {\it New views on some old questions of combinatorial
geometry}, Colloquio Internazionale sulle Teorie Combinatorie
(Roma, 1973), {\bf Tomo I}, pp. 451--468, Accad. Naz. Lincei,
Rome, (1976).

\bibitem{JM15} S.Jendrol', M.Macekov\'{a}, {\it Describing short paths in plane graphs of
girth at least $5$}, Discrete Math., {\bf 338} (2015) 149--158.

\bibitem{JV13} S.Jendrol', H.-J.Voss, {\it Light subgraphs of graphs
embedded in the plane -- a survey}, Discrete Math., {\bf 313, 4}
(2013) 406--421.

\bibitem{Kg55}  A.Kotzig, {\it Contribution to the theory of Eulerian polyhedra},
(Slovak), Mat. \v Cas., {\bf 5} (1955) 101--103.

\bibitem{Le40}  H.Lebesgue, {\it Quelques cons\'{e}quences simples de la formule d'Euler},
J. Math. Pures Appl., {\bf 19} (1940) 27--43.

\bibitem{We04} P.Wernicke, {\it \"Uber den Kartographischen Vierfarbensatz}, Math. Ann.,
{\bf 58} (1904) 413--426.


\end{thebibliography}
\end{document}
