text:
\begin{document}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{con}[thm]{Conjecture}
\newtheorem{claim}[thm]{Claim}
\newtheorem{obs}[thm]{Observation}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{rmk}[thm]{Remark}
\newcommand{\di}{\displaystyle}
\def\dfc{\mathrm{def}}
\def\cF{{\cal F}}
\def\cH{{\cal H}}
\def\cT{{\cal T}}
\def\C{{\mathcal C}}
\def\cA{{\cal A}}
\def\cB{{\mathcal B}}
\def\P{{\mathcal P}}
\def\Q{{\mathcal Q}}
\def\cP{{\mathcal P}}
\def\cp{\alpha'}
\def\Frk{F_k^{2r+1}}

\newcommand{\F}{\mathcal{F}}

\title{Covering $2$-connected $3$-regular graphs with disjoint paths}
\author{Gexin Yu}
\address{Department of Mathematics\\
The College of William and Mary\\
Williamsburg, VA, 23185, gyu@wm.edu.}

\thanks{The research is supported in part by the NSA grant  H98230-16-1-0316.}

\date{\today}

\maketitle

\begin{abstract}
A path cover of a graph is a set of disjoint paths so that every vertex in the graph is contained in one of the paths.    The path cover number $p(G)$ of graph $G$ is the cardinality of a path cover with the minimum number of paths.    Reed in 1996 conjectured that a $2$-connected $3$-regular graph has path cover number at most $\lceil n/10\rceil$.   In this paper, we confirm this conjecture.

\medskip
\noindent{\bf Keywords:}  Path cover, regular graphs, discharging

\noindent{\bf AMS subject class:} 05C38, 05C70
\end{abstract}

\section {Introduction}

A {\em path cover} of a graph is a set of disjoint paths that contain all the vertices of the graph. The {\em path cover number} of graph $G$, written as $p(G)$, is the cardinality of a path cover with the minimum number of paths.

Ore~\cite{O61} initiated the study of path covers.  A graph has path cover number $1$ precisely when it has a Hamiltonian path.  It is well-known that if the minimum degree of an $n$-vertex graph is at least $n/2$ then the graph is Hamiltonian.  Because of its natural connection with hamiltonian graphs, people were interested in the sufficient conditions for a graph to have path cover number at most $k\ge 2$, see, for example, \cite{H88, N75}.   In more recent years, path covers have been used to study other graph parameters,  such as domination numbers~\cite{R96, KS05, LR08},  $L(2,1)$-labelling~\cite{GMW94},  independence number~\cite{H88}, and graphic-TSP~\cite{FRS14}, just to name a few.

Every $n$-vertex graph have a path cover of order at most $n$, and one would imagine that a graph with more edges will require fewer paths to cover. However, an $n$-vertex graph with minimum degree $t$ could have path cover number as high as $n-2t$, for example $K_{t, n-t}$.  Thus,  we are more interested in path cover of regular graphs.   Jackson~\cite{J80} showed that $2$-connected $k$-regular graphs with at most $3k+1$ vertices have a hamiltonian path (actually they have a hamiltonian cycle except the Petersen graph), thus the path cover number is $1$. Magnant and Martin~\cite{MM09} studied path cover numbers of $k$-regular graphs for $k\ge 3$, and they showed that for $k\le 5$, a $k$-regular graph has path cover number at most $n/(k+1)$, which they conjectured to be true for $k>5$.  Note that if every component of a graph $G$ is a clique of $k+1$ vertices, then $p(G)=n/(k+1)$, thus the bound is sharp for general graphs.  As they pointed out,  it is more difficult to find the path cover numbers of connected regular graphs.

The following example gives a general lower bound for the path cover numbers of connected $k$-regular graphs. Take $K_{2, k-1}$ and replace every vertex of degree $2$ with $K_{k+1}^-$ (a $k+1$-clique minus an edge), and call this graph $H$, in which two vertices have degree $k-1$ and the rest have degree $k$. Now let $G$ be the $k$-regular graph with $n$ vertices formed from $\frac{n}{k^2+1}$ pairwise disjoint $H$ by adding $\frac{n}{k^2+1}$ edges to link them in a ring.   It is not hard to see that the path cover number of $G$ is at least $\frac{n(k-3)}{k^2+1}$ for $k\ge 5$. Therefore for $k\ge 13$,  one cannot find a path cover with fewer than $n/(k+4)$ paths in connected $k$-regular graphs (note that the examples are actually $2$-connected).  Some more examples from \cite{OW10, OW11} also show that $n/(k+4)$ paths are necessary.

Intuitively, one may need more paths to cover the vertices when there are fewer edges in the graphs.  This initiated the study of path covers for connected $3$-regular graphs. Reed~\cite{R96} showed that {\em a connected $3$-regular graph with $n$ vertices has path cover number at most $\lceil n/9\rceil$}, and also gave examples that need $\lceil n/9\rceil$ paths.    He conjectured \cite{R96} that  it suffices to use at most $\lceil n/10\rceil$ paths to cover $2$-connected $3$-regular graphs.  In this article, we confirm this conjecture.

\begin{thm}\label{main}
Every $2$-connected $3$-regular graph with $n\ge 10$ vertices has path cover number at most $n/10$.
\end{thm}

It follows that every $2$-connected $3$-regular graph with at most $20$ vertices contains a hamiltonian path.
Reed~\cite{R96} gave the following example to show that one cannot improve $\lceil n/10\rceil$ in general:    let $C=u_1v_1u_2v_2\ldots u_kv_k$ be a cycle of $2k$ vertices, let $H$ be the the graph obtained from the Petersen graph by removing an edge, say $uv$, and let $G$ be the graph obtained by replacing edge $u_iv_i$ for $1\le i\le k$ with $H$ so that $u=u_i$ and $v=v_i$.  He claimed that the path cover number of $G$ is $n/10$, based on the observation that one needs a path to cover each $H$.   However, we can use one path to cover two consecutive copies of $H$, thus only need $n/20$ paths to cover $V(G)$.    Here we give infinitely many $2$-connected $3$-regular $n$-vertex graphs whose path cover numbers are at least $n/14$.

\begin{thm}
There are infinitely many $2$-connected $3$-regular $n$-vertex graphs whose path cover numbers are at least $n/14$.
\end{thm}

\begin{proof}
 Let $G$ be an arbitrary 2-connected 3-regular graph, and let $H$ be the graph obtained from $G$ by replacing each edge of $G$ with a $K_4^-$ (that is, delete the edge, and connect two endpoints of the edge to the two degree-2 vertices on $K_4^-$, respectively).  Then $n(H)=n(G)+4\cdot \frac{3n(G)}{2}=7n(G)$.  We now show that $p(H)\ge n(G)/2=n(H)/14$.

Let $\P$ be a path cover of $H$.  Let $e=uv$ be the edge between $u\in V(G)$ and $v$ in some $K_4^-$.  Then either $uv$ is on a path of $\P$, or $v$ is on some path in $\P$ that contains all vertices of the $K_4^-$.  In the latter case, we may reroute the path so that $v$ is an endpoint, thus extend the path to include the edge $vu$.  Therefore, we may obtain a path decomposition $\P'$ of $G$ (a set of edge-disjoint paths $\P'$ containing all the edges of $G$) with $|\P'|=|\P|$.   Each path in $\P'$ contains a vertex in $G$ as either an internal point or an endpoint, and only when it is an endpoint, the parity of its degree changes when we remove the edges on the path.  But each path can only change the degree parities of at most two vertices in $G$.  As $G$ has $n(G)$ vertices whose degree parity need to be changed, there are at least $n(G)/2$ paths in $\P'$.   Thus,  $\P$ contains at least $n(H)/14$ paths.
\end{proof}

 It is an interesting question to determine the sharp bounds for the path cover numbers of $2$-connected $3$-regular graphs in terms of the orders of the graphs. \\

We will often use the following notation for a path and its segments.
A {\em $k$-path} is a path of $k$ vertices. For a $k$-path $P$, if $G[V(P)]$ contains a spanning cycle, we call it a {\em cyclic $k$-path} or a {\em $k$-cycle}, otherwise {\em non-cyclic}.   A vertex on a non-cyclic path $P$ is called {\em weighty} if it is adjacent to an endpoint of $P$ by an edge not on $P$.   If a path $P$ contains vertex $x$, then we sometimes write $P$ as $P_v$, and let $v^-, v^+$ be the vertices (neighbors) next to $v$ on $P$, respectively.  If the endpoints of $P_v$ are $x$ and $y$, then we also write $P_v$ as $xPy$,  or even as $xPv^-vv^+Py$.  We will use $uPv$ to denote the segment on $P$ from $u$ to $v$. If $v$ is an endpoint of $P_v$, we sometime use $P_vv$ to denote the path $P_v$ with endpoint $v$.  For other notation, we refer to West~\cite{W01}.

\section{Sketch of the proof of Theorem~\ref{main}}

The idea of the proof of the theorem is quite simple.  We consider a specially chosen minimal path cover $\P$, and assign a weight of $10$ to each path in the cover initially. We then redistribute the weights among the paths and show that the final weight on each path is at most its order.  It follows that the total weight is $10|\P|$ on one hand, and at most $n$ on the other hand, therefore $|\P|\le n/10$.  The difficulty lies on the choice of minimal path cover and on the way to redistribute the weights.  Below we give some insights on how we make the choices.

In the minimal path covers we can show that none of the paths are single vertices or contain a spanning cycle.  We may think that the weights of the paths are all on the endpoints, 5 for each.  Let $x$ be an endpoint of a path $P$, and $xu$ be an edge not on $E(P)$.  Clearly, $u$ is not an endpoint of another path, or we will combine the paths into one to get a cover with fewer paths.    We transfer a weight of $2$ from $x$ to $u$.  The vertex $u$ is called {\em weighty} if $u$ is on $P$ and {\em heavy} otherwise.  Then on each path, the four edges incident with the endpoints will send out a weight of $8$ and only a weight of $1$ remains on each endpoint.

Note that heavy vertices are not next to each other on the paths, or we can rearrange the paths to get a cover with fewer paths.  Therefore, if there are no consecutive vertices on paths that are either heavy or weighty, and the number of vertices on a path is not odd, then the final weight on each path is at most the number of vertices on the path, as desired.  Therefore the problematic cases are the existence of consecutive weighty and heavy vertices,  or the number of vertices is odd and every other vertex on a path is weighty or heavy.  They force us to identify more vertices to transfer weights from one path to another, and suggest such vertices to be the ones incident with a vertex whose neighbors are weighty and heavy on the path.  It turns out that we only need to use such vertices, namely {\em P(seudo)E(ndpoint)-vertices}, to transfer a weight of $1$.  PE-vertices share a lot of common features with the endpoints.  For example, a light vertex cannot be next to a heavy vertex on a path, where a light vertex is the neighbor of a PE-vertex not on the path of the PE-vertex.  Light vertices make the proof more complicated.

There are still bad situations that a path may have too much weight. For example, a 3-path with a heavy middle vertex, or a $5$-path $P=xu_1u_2u_3y$ such that $xu_2, xu_3\in E(G)$, or a $6$-path $P=xu_1u_2u_3u_4y$ such that $xu_3, x'u_1, x'u_4\in E(G)$ where $x'$ is an endpoint of another path, or a $7$-path $P=xu_1u_2u_3u_4u_5y$ such that $xu_4, x'u_1, x'u_5\in E(G)$ where $x'$ is an endpoint of another path. Fortunately, we can carefully define the optimal path covers to avoid all those situations.

Each pair of consecutive heavy/weighty vertices on a path contains a neighbor of the endpoints, so there are at most four such pairs on each path.  To show that each path has no more weight than its number of vertices, we show that in each of the bad cases, the path has enough neutral vertices (vertices do not receive weights) and/or PE-vertices.

We define optimal path covers and study their properties in Section~\ref{optimal}. The special vertices (heavy, light, PE-vertices) and their properties are studied in Section~\ref{structure}.  Then in Section~\ref{counting}, we prove the main lemma that the total weight on each path does not exceed its order and finish the proof of the theorem.

\section{Optimal path covers and their basic properties}\label{optimal}

Let $G$ be a minimum counterexample to Theorem~\ref{main}.  Among all path covers of $G$, choose $\P$ to be an optimal path cover subject to the following:
\begin{enumerate}[(i)]
\item the number of paths is minimized.
\item subject to (i), the number of $1$-paths is minimized.
\item subject to (i)-(ii), the number of $3$-paths and cyclic paths is minimized.
\item subject to (i)-(iii), the number of bad endpoints is minimized, where an endpoint $x'\in P'\in \P$ is bad if
(v1) $x'$ is adjacent to $u_1, u_4\in P$ and $xu_3\in E(G)$, or
(v2) $x'$ is adjacent to $u_1, u_5\in P$ and $xu_4\in E(G)$, where $P=xu_1u_2u_3u_4\ldots u_ky\in \P-\{P'\}$.
\item subject to (i)-(iv), the number of annoying endpoints is minimized, where an endpoint $x'\in P'=x'u'_1\ldots u'_ly'$ is annoying if $x'u'_{s+1}, x'u_i, xu'_{s-1}, u'_su_{i+1}\in E(G)$ with $P=xu_1u_2\ldots u_ky\in \P-\{P'\}$ and $2\le s\le l-1$.
\item subject to (i)-(v), the number of weighty vertices is minimized.
\item subject to (i)-(vi), for each non-cyclic path $P$, the number of vertices on $P$ between the endpoints and their corresponding furthest neighbors on $P$ is maximized.
\end{enumerate}

We shall call a path cover satisfying the first $t$ conditions above as $\P_t$. Thus $\P$ is $\P_7$, and $\P_0$ is just a path cover to $G$.  Clearly, $\P_{i+1}\subseteq \P_i$, so $\P_{i+1}$ has all the properties that $\P_i$ has.

A {\em net} is a triangle whose three neighbors not on the triangle are distinct.  The following was observed in ~\cite{R96}.

\begin{lem}\label{net}
The graph $G$ contains no net.
\end{lem}

\begin{proof}
For otherwise, let $u_1u_2u_3$ be a triangle with $u_iu_i'\in E(G)$ such that $u_i'$'s are distinct. Then we contract the triangle to a single vertex $u$ and get a graph $G'$.  Now $G'$ has a path cover with at most $|V(G')|/10$ paths, but then we can get a path cover of $G$ by replacing $u$ with a path containing $u_1, u_2, u_3$.
\end{proof}

\begin{lem}\label{basic-facts}The following are true about $\P_1$:
\begin{enumerate}[(1)]
\item Endpoints of different paths in $\P_1$ are not adjacent. In particular, there is no edge between cyclic paths or between a cyclic path and an endpoint of a non-cyclic path.
\item every cyclic path has at least two neighbors not on the path.
\end{enumerate}
\end{lem}

\begin{proof}
(1) is true because our cover used the minimum number of paths. (2) is true because $G$ has no cut-vertices.
\end{proof}

The following lemma from~\cite{MM09} says that a path cover subject to (i) and (ii) contains no $1$-paths.  We give an alternative proof here, whose idea will be used to prove more results about path covers.

\begin{lem}[\cite{MM09}]\label{mmlem}
The path cover $\P_2$ contains no $1$-paths.
\end{lem}

\begin{proof}
Suppose that $P\in \P_2$ consists of vertex $v$.  By Lemma~\ref{basic-facts}, $v$ is not adjacent to an endpoint of another path. We also note that $v$ is not adjacent to an interior vertex on a path $P'$ of order at least $4$, for otherwise, one can easily decompose $P\cup P'$ into two paths, each of order at least $2$. Therefore $v$ must be adjacent to the midpoints of $3$-paths.  Furthermore, if $v$ is adjacent to the vertex $w\in P'=xwy$, then we may rearrange paths to form the paths $xwv$ and $y$ or $vwy$ and $x$. This implies $x$ and $y$ must also be adjacent only to the midpoints of 3-paths.

Let $T$ be the set of $1$-paths and $3$-paths that are  involved in the above rearrangement process.  We consider an auxiliary digraph $D$ whose vertices are the paths in $T$, and there is a directed edge from $P_1\in T$ to $P_2\in T$ if and only if an endpoint of $P_1$ is adjacent to the midpoint of $P_2$.  Clearly, each vertex in $D$ has in-degree at most $1$ and out-degree at least $3$, which is impossible.  Therefore, $\P$ contains no $1$-paths.
\end{proof}

\begin{lem}\label{no-triangle}
The path cover $\P_3$ contains no $1$-paths, $3$-paths, or cyclic paths.
\end{lem}

\begin{proof}
We call a path {\em bad} if it is cyclic or has order $1$ or $3$.   By Lemma~\ref{mmlem}, we may assume that each bad path in $\P_3$ is a non-cyclic 3-path (note that a cyclic 3-path must be a net) or a cyclic path with order at least $4$.

Let $P$ be a bad path in $\P_3$ and $x\in P$ be a potential endpoint of $P$, which is an endpoint if $P$ is non-cyclic, or any vertex on $P$ if $P$ is cyclic.  Suppose that $xw\in E(G)$ with $w\in Q\in \P_3-\{P\}$.  Then $Q$ is not cyclic, and $Q-w$ splits into two paths $Q_1$ and $Q_2$.    In fact, the path $P'$ obtained by concatenating $P, w, Q_i$ cannot be cyclic (as then $P+Q$ would have a Hamilton path contradicting minimality) or have length less than $4$. Thus both $Q_1$ and $Q_2$ must be bad by the minimality of the cover. Furthermore, neither $Q_1$ nor $Q_2$ is a cyclic 3-path, or we would have a net or a path cover with fewer paths.    We shall call $w$ a {\em special vertex} on $Q$, and $Q_1, Q_2$ {\em bad components} on $Q$.

Now, for $i\in \{1,2\}$, provided $Q_i$ has order more than one,  replacing $P,Q$ in $\P$ with $Q_i$ and $P'=P+w+Q_{3-i}$ gives a new minimal path cover. We can repeat our argument using $Q_i$ in the place of $P$ and any other non-bad path of the new cover other than $P'$ in the place of $Q$.

We build a directed graph whose vertices are the paths in $\P$, and a family $\F$ of subpaths of these paths as follows.
\begin{itemize}
\item[(A)] The set $\F_0$ consists of bad paths in $\P_3$; and we add a directed edge from $P\in \F_0$ to $Q\in \F_0$ if a potential endpoint of $P$ is adjacent to a special vertex on $Q$ (note that this can only happen if $Q$ is a non-cyclic $3$-path);

\item[(B)] If an endpoint of a Hamilton path on the vertex set of a bad path $P\in \F_0$ is adjacent to $w$ on a non-bad path $Q\in \P$, we add to $\F_1$ all the bad components of $Q-w$ which do not have order $1$, and add to our digraph an edge from $P$ to $Q$;

\item[(C)] For $i\ge 1$,  if an endpoint of a Hamilton path on the vertex set of some bad path $P\in \F_i$ is adjacent to a special vertex $w$ of some non-bad path $R\in \P_3$, we add to $\F_{i+1}$ all the components of $R-w$ which do not have order $1$,  and we add to the digraph the edge from the path in $\P_3$ that contains $P$ as a bad component described in (B) to $R$.  Note that multi-edges are allowed, but we only allow one directed edge implied by the middle vertex of each 5-path.
\end{itemize}

We let $\F$ be the union of the $\F_i$.  By definition, the in-degree of a path equals to the number of special vertices on it.  Note that a cyclic bad path or component does not contain special vertices.  It follows that if a non-bad path $P$ contains two special vertices $w_1$ and $w_2$, then the bad component in $P-w_1$ that contains $w_2$ must be a $3$-path, and the bad component in $P-w_2$ that contains $w_1$ must also be a $3$-path, so $P$ must be a non-cyclic $5$-path.  Therefore, the in-degrees of $5$-paths are at most $2$ and all other paths are at most $1$. Note that there may be isolated vertices in the digraph.

Now we count the out-degrees. The out-degree of a path $P$ equals to the number of edges that connect one endpoint of a bad component of order more than $1$ and a special vertex not on $P$.  Let $Q_1, Q_2$ be the two bad components of a path $P\in \P_3$ in the digraph.

If $Q_1$ and $Q_2$ both have order $1$, then $P$ is a bad $3$-path.  By (A), $P$ has out-degree $4$.  So let $Q_1$ have order more than $1$.  Note that $Q_1$ has at least two edges out of $Q_1$ (as $G$ is $2$-connected), one of which is not adjacent to the special vertex on $P$.

If $Q_1$ and $Q_2$ are both cyclic or have order $1$, then there can be no edge between them, as if $Q'=Q_1\cup Q_2$ has a Hamiltonian cycle, we can rearrange $P\cup Q$ into one path, contradicting the minimality of the cover, and otherwise $P'=P+w$ and $Q'$ are both non-cyclic and  we contradict the minimality of the number of bad paths in the cover.    So $P$ has out-degree at least $1$ (actually $2$ if both $Q_1, Q_2$ are cyclic).

Now, if $Q_1$ has order three and $Q_2$ is cyclic or has order $1$, then (a) the endpoint of $Q_1$ which is an endpoint of $Q$ cannot be adjacent to any vertex on $Q_2$ or we could find a Hamilton path on $P\cup Q$ contradicting the minimality of the cover, and (b) the other endpoint $x'$ of $Q_1$ can be adjacent to none of the vertices on $Q_2$ or we could find a Hamiltonian path $P'$ on $P\cup Q_2+w+x'$, which together with $Q′=Q_1-x'$ contradicts the minimality of the cover.   Similar arguments show that if $Q_1$ and $Q_2$ both have order three then there are no edges joining their endpoints.  So $P$ has out-degree at least $3$.

Since the out-degrees of the paths are as large as their in-degrees, and the bad paths have higher out-degrees than their in-degrees, such a digraph does not exist, a contradiction.
\end{proof}

From now on, we assume that $\P_3$ consists of non-cyclic paths with order other than $1$ and $3$.

\begin{lem}\label{no-7}
There are no bad endpoints described in (iv) in $\P_4$.
\end{lem}

\begin{proof}
Suppose otherwise.  Consider an endpoint $x'\in P'=x'u_1'u_2'\ldots u_t'y'$ in (v1).  We replace $P,P'$ with $P'x'u_1x$ and $u_2Py$.   We lose $x'$, and do not create cyclic paths or we would contradict the minimality of the cover.  We do not gain a new bad endpoint described in (v1) because (a) $x$ is not adjacent to $u_1'$ or we could rearrange $P'+P$ into one path $P'u_1'xu_3u_2u_1x'u_4Py$, and (b) $u_2$ is not adjacent to $u_5$ or we could rearrange $P'+P$ into one path $P'x'u_4u_3xu_1u_2u_5Py$.  We also do not gain a new bad endpoint described in (v2) because (a) $x$ cannot be, or $u_2u_6, xu_7\in E(G)$, which allows us to reroute $P,P'$ into one path $P'x'u_1u_2u_6u_5u_4u_3xu_7Py$, and (b) $u_2$ cannot be, or $u_2u_3', xu_2'\in E(G)$, which allows us to reroute $P, P'$ into one path  $P'u_3'u_2u_1x'u_1'u_2'xu_3u_4Py$.

Consider an endpoint $x'\in P'$ in (v2).  If $u_5Py$ is a $3$-path, then we replace $P,P'$ with $u_6y$ and $xPu_5x'P'$.  We lose $x'$, and do not create cyclic paths, but clearly do not gain a new bad endpoint, as $u_1$ is now adjacent to a vertex on the path, and $u_6$ has at most one neighbor on other paths.  If $u_5Py$ is not a $3$-path, then we replace $P,P'$ with $u_5Py$ and $u_2u_3u_4xu_1x'P'$.  We lose $x'$, and do not create cyclic paths.  We do not gain new bad endpoints, since $u_2, u_5$ cannot be as they have at most one neighbor on other paths, and no other vertex can be adjacent to $x'$ as it is already adjacent to $u_5, u_1, u_1'$, and no vertex from other path can be a bad endpoint (to $u_5Py$) as $u_5$ has only one neighbor on the path.
\end{proof}

\begin{lem}\label{annoying}
There are no annoying endpoints described in (v) in $\P_5$.
\end{lem}

\begin{proof}
Let $x'\in P'=x'u'_1\ldots u_l'y'\in \P_5$ be an annoying endpoint. Then for $P=xu_1\ldots u_ky\in \P_5-\{P'\}$, $x'u_i, x'u'_{s+1}, xu'_{s-1}, u'_su_{i+1}\in E(G).$  Note that $P,P'$ can be decomposed into $yPu_{i+1}u_s'P'y'$ and cyclic path $x'P'u_{s-1}'xPu_i$. So $y, y'$, and endpoint of the paths in $\P_5-\{P,P'\}$ cannot have neighbors on the cyclic path.

{\bf Case 1.} $s=3$ and $u_1'u_{i+2}\in E(G)$.  We replace $P, P'$ with $P_1=x'u_1'$ and $P_1'=yPxu_2'P'y'$.  Since $P_1$ is a $2$-path and $xy, xy'\not\in E(G)$,  $P_1, P_1'$ are not $1$-paths, $3$-paths, or cyclic paths, and none of the endpoints ($x', u_1', y, y'$) becomes bad or annoying.  But we have fewer annoying endpoints, a contradiction.

{\bf Case 2.} $s>3$, or $s=3$ but $u_1'u_{i+2}\not\in E(G)$.  We replace $P,P'$ with $P_2=u_iPxu_{s-1}'P'x'u_{s+1}'P'y'$ and $P_2'=u_s'u_{i+1}u_{i+2}Py$.   Note that none of $P_2, P_2'$ can be $1$-paths, $3$-paths, or cyclic paths. Since $u_i$ has at most one neighbor on paths other than $P_2$, $u_i$ is not bad.  Since $u_{s-1}'$ is nto next to $u_i$ (the endpoint of $P_2$), $u_s'$ is not bad.  Since $u_s'$ has only one neighbor on $P_2'$, it is not annoying.  Note that $u_i$ is annoying only if $u_1'u_{i+2}\in E(G)$ and $s=3$ (so that $u_{s-1}'=u_2'$), so $u_i$ is not annoying.  Since $y, y'$ have no neighbors in $u_iP_2x'$, they cannot become new bad or annoying endpoints.  Therefore, we have fewer annoying endpoints, a contradiction.
\end{proof}

\begin{lem}\label{no-two-consecutive}
Let $P=xu_1u_2\ldots u_ky\in \P_7$ be a non-cyclic path so that $xu_i,xu_j\in E(G)$ with $1<i<j\le k$.  Then $j\not=i+1$, and the neighbors of $u_{i-1}$ and $u_{j-1}$ are on $P$.  Furthermore, if $y$ has no neighbors on $xPu_j$, then the neighbors of $u_{j-1}$ and $u_{i-1}$ must be on $xPu_j$.
\end{lem}

\begin{proof}
If $j=i+1$ and $i\not=2$, then $xu_iu_{i+1}$ is a net, a contradiction to Lemma~\ref{net}. If $j=i+1=3$, then $u_1$ will be a better endpoint than $x$ subject to (vi) (with fewer weighty vertices) or (vii) (weighty neighbors are further away from the endpoints).   Let $j>i+1$.  If $u_{i-1}$ (or $u_{j-1}$) has a neighbor outside of $P$, then we can reroute $P$ so that $u_{i-1}$ (or $u_{j-1}$) is an endpoint, which would give fewer weighty vertices,  a contradiction to the optimality of $\P$.   If $y$ has no neighbors on $xPu_j$, and $u_{j-1}$ (or $u_{i-1}$)  has a neighbor $u_t$ with $t>j$, but then $u_{j-1}$ (or $u_{i-1}$) is a better endpoint than $x$ subject to (vii) (and we do not change the number of vertices between $y$ and its furthest neighbor).
\end{proof}

\section{Properties of heavy, light, and PE-vertices}\label{structure}

In this section, we study the properties of some special vertices on the paths in $\P$.

\begin{definition}
Let $u$ be an endpoint of a path $P\in \P_4$ and $uv\in E(G)-E(P)$.  Then $v$ is called a heavy vertex if $v\not\in V(P)$ (and a weighty vertex is $v\in V(P)$).
\end{definition}

\begin{definition}
Let $uv$ be an edge between $u=u_i\in P=xu_1\ldots u_ky\in \P_4$ and $v\in P_v\in \P_4-\{P\}$. Then $u$ is called a PE-vertex (aka, pseudo-endpoint) and $v$ is called a light vertex if one of the following is true
\begin{enumerate}
\item[(1a)] $xu_{i+1},yu_{i-1}\in E(G)$; or
\item[(1b)] $xu_{i+1}\in E(G)$, and $u_{i-1}$ is heavy;  or $yu_{i-1}\in E(G)$ and $u_{i+1}$ is heavy; or
\item[(1c)] both $u_{i-1}$ and $u_{i+1}$ are heavy.
\end{enumerate}
A vertex is {\em neutral} if it is not heavy or light or weighty.
\end{definition}

 Note that a PE-vertex is also a neutral vertex. Also note that if $u$ is a PE-vertex defined in (1a) and (1b), then $P_u$ can be rerouted so that $u$ (and $x$ or $y$) is an endpoint of the path.

\begin{lem}\label{neutral-end}
Let $u\in P\in \P, v\in P_v\in \P-\{P\}$ with $uv\in E(G)$. If $P=xPy$ can be rerouted so that $u$ is an endpoint, then $v$ cannot be an endpoint or a PE-vertex, unless $xv^-, yv^+\in E(G)$. Consequently, if $u$ and $y$ are the endpoints, then $ux\in E(G)$ or $u$ is neutral.
\end{lem}

\begin{proof}
If $P_v$ can also be routed so that $v$ is an endpoint, then $P, P_v$ can be combined into one path, a contradiction. So $v$ cannot be an endpoint or a PE-vertex defined as in (1a) or (1b).

Let $v$ be a PE-vertex defined as in (1c). Let $P_v=x_vP_vv^-vv^+P_vy_v$.  Then $v^-$ and $v^+$ are heavy. We assume that $v^-x_s, v^+x_t\in E(G)$, where $x_s, x_t$ are endpoints of $P_s, P_t\in \P-\{P_v\}$, respectively.  If one of $P_s$ and $P_t$, say $P_s$, is not $P$, then we can decompose $P, P_s, P_v$ into two paths: $P_sx_sv^-P_vx_v$ and $y_vP_vvuP$, a contradiction.  So $P_s=P_t=P$.  If $y$ (and by symmetry, $x$) has only one neighbor on $P$, then $y$ must be  the other endpoint when $u$ is an endpoint of $P$, thus $yv^+\not\in E(G)$ (and similarly, $yv^-\not\in E(G)$),  or $P, P_v$ can be combined into one path $y_vP_vv^+yPuvP_vx_v$.  It follows that $xv^-, xv^+\in E(G)$, and thus $x$ has only one neighbor on $P$, a contradiction. So both $x$ and $y$ have at least two neighbors on $P$. Then we must have $xv^-, yv^+\in E(G)$.

When $u$ and $y$ are the endpoints, $v$ cannot be an endpoint or a PE-vertex, so $u$ is not heavy or light and $uy\not\in E(G)$. Then $u$ is neutral or weighty, and when it is weighty, we have $xu\in E(G)$.
\end{proof}

\begin{cor}\label{neutral}
Let $P=xu_1\ldots u_ky\in \P$ and $1\le i<j\le k$. Then
\begin{itemize}
\item if $xu_j\in E(G)$, then $u_{j-1}$ is neutral;
\item if $xu_{i+1}\in E(G)$ and $u_iu_j\in E(G)$, then $u_{j-1}$ is neutral or $xu_{j-1}\in E(G)$;
\item if $xu_{j+1}\in E(G)$  and $u_iu_j\in E(G)$, then  $u_{i+1}$ is neutral or $xu_{i+1}\in E(G)$;
\item if $xu_{j-1}\in E(G)$  and $u_iu_j\in E(G)$, then $u_{i-1}$ and $u_{i+1}$ are neutral or adjacent to $x$;
\item if $xu_{i+1}, xu_{j+1}, u_iu_j\in E(G)$, then $u_1, u_{j-1}$ are neutral.
\end{itemize}
\end{cor}

\begin{cor}\label{no-neighbor-of-y}
Let $P=xu_1\ldots u_ky\in \P$. If $xPu_i$ is cyclic and $u_{i+1}$ is heavy or light, then a vertex $u\in xPu_{i-1}$ is adjacent to $y$ or $u_j$ with $yu_{j-1}\in E(G)$ only when $u_{i+1}$ is light and is adjacent to $v_s\in P'=x'P'v_{s-1}v_sv_{s+1}P'y'$ such that $xv_{s-1},yv_{s+1}\in E(G)$.

\end{cor}

\begin{proof}
Under the condition, $P$ can be rerouted so that $u_{i+1}$ is an endpoint.  So the statement follows from Lemma~\ref{neutral-end}.
\end{proof}

\begin{lem}\label{25-well}
PE-vertices form an independent set. Consequently, no light vertex is a PE-vertex.
\end{lem}

\begin{proof}
Let $u, u'\in E(G)$ be PE-vertices such that $uu'\in E(G)$ with $u\in P_u=xPu^-uu^+Py$ and $u'\in P_{u'}=x'Pu'^-u'u'^+Py'\in \P-\{P\}$.   By Lemma~\ref{neutral-end}, we may assume that $u, u'$ are PE-vertices defined as in (1c), thus assume that $u^-, u^+, u'^-, u'^+$ are adjacent to endpoints $s\in P_s, t\in P_t, s'\in P_{s'}, t'\in P_{t'}$, respectively, where $P_s, P_t\not=P_u$ and $P_{s'}, P_{t'}\not=P_{u'}$.

First assume that none of the pairs $(P_s, P_{s'}), (P_s, P_{t'}), (P_t, P_{s'}), (P_t, P_{t'})$ contains two different paths. Then  $P_s=P_{s'}=P_{t'}=P_t$.  Without loss of generality, we may assume that $s, s'$ are the endpoints of $P_s$. Then $P_u, P_{u'}$ and $P_s$ can be combined into two paths: $xP_uu^-sP_ss'u'^-P_{u'}x'$ and $yP_uuu'P_{u'}y'$, a contradiction.  Therefore, without loss of generality, we assume that $P_s\not=P_{s'}$.

If $P_s\not=P_{u'}$ and $P_{s'}\not=P_{u}$, then we reach a contradiction by combining $P_u, P_s, P_{u'}, P_{s'}$ into three paths: $P_su^-P_ux, P_{s'}u'^-P_{u'}x'$ and $yP_uuu'P_{u'}y'$.  Thus,  we may assume that $P_s=P_{u'}$ and let $s=x'$.

If $P_{s'}\not=P_u$,  we can decompose $P_{s'}, P_u, P_{u'}$ into fewer paths: $xP_uu^-x'P_{u'}u'^-s'P_{s'}$ and $yPuu'P_{u'}y'$, again a contradiction.  Therefore, we may assume that $P_{s'}=P_u$.   By symmetry, we also know that $P_t=P_{u'}$ and $P_{t'}=P_u$.

Let $xu'^-\in E(G)$.   If $x'u^+\in E(G)$ (or by symmetry $y'u^-\in E(G)$), then we reach a contradiction by combing $P_u$ and $P_{u'}$ into one path $yP_uu^+x'P_{u'}u'^-xP_uuu'P_{u'}y'$. Thus,  we let $x'u^-, y'u^+\in E(G)$. But we again can combine the two paths into one path $yP_uu^+y'P_{u'}u'uP_uxu'^-P_{u'}x'$.
\end{proof}

\begin{lem}\label{paired-cycle}
Let $P=xu_1u_2\ldots u_ky\in \P_4$. Assume that for some $1<s<i<t<k$,  the subgraphs induced by $V(xPu_i)$ and $V(u_{i+1}Py)$ contain spanning paths so that $u_s$ and $u_t$ are the endpoints, respectively.  If $u_s, u_t$ are heavy or light, then
\begin{enumerate}[(a)]
\item $u_s$ and $u_t$ are both light; or
\item $u_s, u_t$ are heavy and adjacent to a same endpoint of $P'\in \P_4-\{P\}$; or
\item $u_s$ is heavy and $u_t$ is light (or by symmetry $u_t$ is heavy and $u_s$ is light) with $x_wu_s, vu_t\in E(G)$, where $x_w$ is an endpoint of $P_w\in \P_4-\{P\}$ and $v\in P_v=x_vP_vv^-vv^+P_vy_v$, such that
\begin{itemize}
\item[(c1)] $P_w=P_v$, and $x_vu_s, x_vv^+\in E(G)$ and $v^-$ is adjacent to $x$ or $y$, or
\item[(c2)] $P_w\not=P_v$, and $v^-, v^+$ are adjacent to $x, y$ or $x_w$.
\end{itemize}
\end{enumerate}
Consequently,  let $xPu_i$ be cyclic, then
\begin{enumerate}
\item if $u_{i+1}$ is heavy, then $xPu_i$ contains at most one heavy or light vertex; and
\item if $u_{i+1}$ is light, then $xPu_i$ contains at most one heavy vertex.
\end{enumerate}
\end{lem}

\begin{proof}
Let $P_1, P_2$ be the spanning paths on $V(xPu_i)$ and $V(u_{i+1}Py)$ so that $u_s, x'$ and $u_t, y'$ are endpoints, respectively.  We may assume that at least one of $u_s, u_t$ (say $u_s$) is heavy, or we have (a).  Let $x_wu_s\in E(G)$ from the endpoint $x_w\in P_w\in \P_4-\{P\}$ and $vu_t\in E(G)$ from $v\in P_v=x_vP_vv^-vv^+P_vy_v\in \P_4-\{P\}$.

Assume first that $P_v$ can be rerouted such that $v$ is an endpoints.   If $v$ is heavy, then we must have (b),  or $P, P_w, P_v$ can be replaced with paths $P_wwuP_1$ and $P_vvu_{i+1}P_2$ to obtain a better path cover.  So let $v$ be light, and by symmetry let $x_vv^+\in E(G)$ and $v^-$ be heavy and adjacent to an endpoint $z\in P_z\in \P-\{P_v\}$.   Then $x_v=x_w$, or we replace $P, P_v, P_w$ with $y_vPv^+x_vP_vvu_tP_2y'$ and $y_wP_wx_wu_sP_1x'$ (when $x_w\not=y_v$) or $x'P_1u_sP_1y_vP_vv^+x_vP_vvu_tP_2y'$ (when $x_w=y_v$).  Now $z$ must be $x$ or $y$, as in (c1), or we could get a cover with fewer paths: $P_1'=P_zzv^-P_vx_vu_sP_1x'$ and $P_2'=y_vP_vvu_tP_2y'$.

Now assume that both $v^-$ and $v^+$ are heavy.  We may assume that $v^-$ is adjacent to an endpoint $z\in P_z\in \P-\{P_v\}$. If $z\not\in \{x,y,x_w\}$, then we can replace $P, P_w, P_z, P_v$ with paths $P_wwuP_1, P_2u_{i+1}vP_vy_v$ and $P_zzv^-P_vx_v$, a contradiction. So $v^-$, and by symmetry $v^+$, is adjacent to $x, y$ or $x_w$, as in (c2).
\end{proof}

\begin{lem}\label{no-consecutive}
The subgraph induced by the set of heavy and light vertices contains no edges.
\end{lem}

\begin{proof}
By Lemma~\ref{25-well}, two vertices that are heavy or light are adjacent only if they are consecutive vertices on a path in $\P$.
Let $u_i, u_{i+1}$ be two vertices on $P$ that are heavy or light.  We may assume that $u_{i+1}$ is adjacent to $x_v$ or the vertex $v$ on $P_v=x_vP_vv^-vv^+P_vy_v\in \P-\{P\}$. As $xPu_i$ and $u_{i+1}Py$ contain spanning trees such that $u_i$ (and $x$) and $u_{i+1}$ (and $y$) are endpoints, respectively, by Lemma~\ref{paired-cycle}, the following are the possible cases:

{\bf Case 1.} both $u_i$ and $u_{i+1}$ are heavy.  Then they are adjacent to the same endpoint $x_v\in P_v$.  In this case, $x_vu_iu_{i+1}$ is a net, which cannot occur by Lemma~\ref{net}.

 {\bf Case 2.} $u_i$ is heavy and $u_{i+1}$ is light.   Then by Lemma~\ref{paired-cycle}, we consider the following cases.

 {\bf Case 2.1.} $x_vu_i, xv^-, vu_{i+1}, x_vv^+\in E(G)$, or $x_vu_i, yv^-, vu_{i+1}, x_vv^+\in E(G)$. In the former case, $x_v$ is an annoying endpoint, which by Lemma~\ref{annoying} cannot exist, and in the latter case, we can combine $P, P_v$ into one path: $xPu_ix_vP_vv^-yPu_{i+1}vP_vy_v$.

 {\bf Case 2.2.} $vu_{i+1}, xv^-, x_wu_i\in E(G)$, where $x_w$ is an endpoint of $P_w\in \P-\{P,P_v\}$, and $v^+$ is adjacent to $y$ or $x_w$.  Then $P, P_v, P_w$ can be combined into two paths: $P_wx_wu_iPxv^-P_vx_v$ and $y_vP_vvu_{i+1}Py$, a contradiction.

{\bf Case 3.} both $u_i$ and $u_{i+1}$ are light.  Then $wu_i, vu_{i+1}\in E(G)$ for PE-vertices $w\in P_w=x_ww_1\ldots w_{s-1}ww_{s+1}\ldots w_ly_w\in \P-\{P\}$ and $v\in P_v=x_vv_1\ldots v_{t-1}vv_{t+1}\ldots v_my_v\in \P-\{P\}$.

 {\bf Case 3.1} $w$ and $v$ are PE-vertices defined as in (1a) or (1b).  Then $P_w$ can be rerouted so that $w$ and $y_w$ are endpoints, and $P_v$ can be rerouted so that $v$ and $y_v$ are endpoints.

\begin{itemize}
\item If $P_w\not=P_v$, then $P, P_v, P_w$ can be combined into paths $P_wwu_iPx$ and $P_vvu_{i+1}Py$, a contradiction.
\item If $P_w=P_v$, then $x_w$ or $y_w$ cannot be adjacent to two weighty vertices, by Lemma~\ref{no-two-consecutive}, so we may assume that $x_ww_{s+1}\in E(G)$ and $v=w_j$ so that $y_ww_{j-1}\in E(G)$. Clearly, $j<s$, or $P, P_w$ can be combined into one path $xPu_iwP_wx_ww_{s+1}P_ww_{j-1}y_wP_ww_ju_{i+1}Py$. By definition, $w_{j+1}$ is heavy is adjacent to an endpoint $z\in P_z\not=P_w$, so $P, P_w, P_z$ can be decomposed into paths $P_zzw_{j+1}P_ww_su_iPx$ and $yPu_{i+1}w_jP_wx_ww_{s+1}P_wy_w$, a contradiction.
\end{itemize}

{\bf Case 3.2} $w$ is a PE-vertex defined as in (1a) or (1b), and $v$ is a PE-vertex defined as in (1c).  Let $x_ww_{s+1}\in E(G)$.  By definition, $v_{t-1}$ and $v_{t+1}$ are heavy, then at least one of them, say $v_{t-1}$, is not adjacent to $x_w$.  Let $v_{t-1}$ be adjacent to the endpoint $z\in P_z\not=P_v$. When $P_z=P$, we assume that $z=y$.
\begin{itemize}
\item  If $P_v\not=P_w$,  then $P, P_w, P_v, P_z$ can be decomposed into fewer paths: $$P_zzv_{t-1}P_vx_v,\   y_vP_vvu_{i+1}Py,\  P_wwu_iPx.$$
\item If $P_v=P_w$ and $v=w_j$ with $j>s$, then $P, P_w, P_z$ can also be decomposed into fewer paths: $P_zzw_{j-1}P_ww_{s+1}x_wP_wwu_iPx, \quad  y_wP_ww_ju_{i+1}Py.$
\item If $P_v=P_w$ and $v=w_j$ with $j<s$, then $P, P_w, P_z$ can be decomposed into fewer paths: $P_zzw_{j-1}P_wx_ww_{s+1}P_wy_w, \quad  xPu_iwP_ww_ju_{i+1}Py.$
\end{itemize}
There is a contradiction in each of the cases.

{\bf Case 3.3.} Both $w$ and $v$ are PE-vertices defined as in (1c).

Let $z_1w_{s-1}, z_2w_{s+1}, z_3v_{t-1}, z_4v_{t+1}\in E(G)$ such that $z_i$ is an endpoint of $P_{z_i}\in\P$, respectively.

Let $P_w\not=P_v$.  As each endpoint is adjacent to at most two heavy vertices, we may assume that $P_{z_1}\not=P_{z_4}$ or $P_{z_1}=P_{z_4}$ and $z_1, z_4$ are the endpoints.  Then $P, P_w, P_v, P_{z_1}, P_{z_4}$ can be decomposed into fewer paths: $P_{z_1}z_1w_{s-1}P_wx_w,\quad P_{z_4}z_4v_{t+1}P_vy_v,\quad   y_wP_wwu_iPx,\quad  x_vP_vvu_{i+1}Py$.

Let $P_w=P_v$.  Assume that $v=w_t$ for some $t>s$.  Note that $P_{z_1}=P_{z_4}$ and $z_1=z_4$, or $P, P_w, z_1, z_4$ can be decomposed into fewer paths:  $xPu_iw_sP_ww_tu_{i+1}Py, P_{z_1}z_1w_{s-1}P_wx_w$ and $P_{z_4}z_4w_{t+1}P_wy_w$.
We may also assume that $P_{z_2}=P_{z_4}$ (and similarly, $P_{z_3}=P_{z_4}$), or $P, P_w, P_{z_2}, P_{z_4}$ can be combined into fewer paths:  $xPu_iwP_wx_w,   P_{z_2}w_{s+1}P_wvu_{i+1}Py,   P_{z_4}z_4w_{t+1}P_wy_w$.
Therefore $P_{z_1}=P_{z_2}=P_{z_3}=P_{z_4}$, and $z_1$ and $z_2$ are the endpoints.  But then $P, P_w$ and $P_{z_1}$ can be combined into two paths:  $xPu_iw_sP_ww_{t-1}z_2P_{z_2}z_1w_{s-1}P_wx_w$ and $yPu_{i+1}w_tP_wy_w$, a contradiction.
\end{proof}

\begin{lem}\label{chord}
Let $P=xu_1u_2\ldots u_ky\in \P_4$ and $u_iu_j\in E(G)$ for some $i,j$ with $j\not=i-1,i+1$.
\begin{enumerate}[(a)]
\item Let $u_{i-1}$ and $u_{i+1}$ be heavy.  Then $u_{j-1}$ is not weighty,  and $u_{j-1}$ is heavy only if $u_{i-1}$ and $u_{j-1}$ are adjacent to the same endpoint of $P'\in \P-\{P\}$;  Similarly,  $u_{j+1}$ is heavy only $u_{i+1}$ and $u_{j+1}$ are adjacent to the same endpoint of $P''\in \P-\{P\}$.  Furthermore, if both $u_{j-1}$ and $u_{j+1}$ are heavy, then $P'=P''$.

\item  Let $xu_{i+1}\in E(G)$ and $u_{i-1}$ be heavy or $yu_{i-1}\in E(G)$.  Then $u_{j-1}$ is neutral when $j>i$, and $u_{j+1}$ is neutral when $j<i$.
\end{enumerate}
\end{lem}

\begin{proof}
(a)   As $u_{i-1}$ and $u_{i+1}$ are heavy,  we may assume that they are adjacent to endpoints $x', x''$ of $P', P''\in \P-\{P\}$, respectively.

First note that $u_{j-1}$ is not weighty. If $xu_{j-1}\in E(G)$, then $P,P'$ can be combined into one path $P'x'u_{i-1}Pxu_{j-1}Pu_iu_jPy$, a contradiction.  If $yu_{j-1}\in E(G)$, then $P, P''$ can be combined into one path $P''x''u_{i+1}Pu_{j-1}yPu_ju_iPx$, a contradiction again.

Note that $u_{i-1}$ and $u_{j-1}$ are the endpoints of the spanning paths $xPu_{i-1}$ and $u_{j-1}Pu_iu_jPy$, respectively.  By Lemma~\ref{paired-cycle}, if $u_{j-1}$ is not neutral, then it is adjacent to $x'$, as claimed,  or it is light as in (c1) or (c2) in Lemma~\ref{paired-cycle}.

If it is the case as (c1), then $u_{j-1}$ is adjacent to a PE-vertex $v\in P'$ such that $x'v^+\in E(G)$. Now $P', P'', P$ can be combined into fewer paths: $P''u_{i+1}Pu_{j-1}vP'x'v^+P'y'$ and $xPu_iu_jPy$. So we may assume that it is the case as (c2).  Then $u_{j-1}$ is adjacent to a PE-vertex $v\in P_v=x_vP_vv^-vv^+P_vy_v\in\P-\{P,P'\}$ such that $v^-, v^+$ are adjacent to $x,y$ or $x'$. We may assume that $v^-$ is adjacent to $x$ or $y$. Then $P', P_v, P$ can be combined into two paths in either case: in the former case $x_vP_vv^-Pu_{i-1}x'P'$ and $y_vP_vvu_{j-1}Pu_iu_jPy$, and in the latter case, $P'x'u_{i-1}Px$ and $x_vP_vv^-yPu_ju_iPu_{j-1}vP_vy_v$, a contradiction.

 For the furthermore part, if both $u_{j-1}$ and $u_{j+1}$ are heavy and adjacent to different paths, say $P'$ and $P''$, then we can replace $P, P', P''$ with $P'x'u_{j-1}Pu_{i+1}x''P''$ and $xPu_iu_jPy$, a contradiction.

(b) When $j>i$, $P$ can be rerouted so that $u_{j-1}, y$ (or $u_{j+1},y$ when $j<i$) are endpoints, it follows from Lemma~\ref{neutral-end} that $u_{j-1}$ is neutral or $xu_{j-1}\in E(G)$; but in the latter case, $P$ can be rerouted so that $u_{i-1}$ and $y$ are endpoints, thus by the same lemma, $u_{i-1}$ cannot be heavy or adjacent to $y$, a contradiction.
\end{proof}

\begin{lem}\label{no-c}
Let $P=xu_1u_2\ldots u_ky\in \P$. If $xu_3\in E(G)$ and $u_4$ is heavy, then $u_1, u_2$ are neutral.
\end{lem}

\begin{proof}
By Lemma~\ref{no-two-consecutive}, $u_2x\not\in E(G)$,  and then by Lemma~\ref{neutral-end},  $u_2$ is neutral, and $u_1y\not\in E(G)$. Assume that $u_1$ is not neutral.  Then $u_1$ must be light or heavy. If $u_1$ is heavy, then by Lemma~\ref{paired-cycle}, $u_1$ and $u_4$ are adjacent to the same endpoint of a path, thus we have a bad endpoint, a contradiction to Lemma~\ref{no-7}. So $u_1$ must be light.

Let $u_1$ be adjacent to the PE-vertex $v\in P_v=x_vP_vv^-vv^+Py_v\in \P-\{P\}$.  Let $u_4$ be adjacent to an endpoint $x_w\in P_w\in \P-\{P\}$.  The following cases (c1) and (c2) from Lemma~\ref{paired-cycle} must be true.

(c1). $P_w=P_v$, and $x_vu_4, x_vv^+\in E(G)$ and $v^-$ is adjacent to $x$ or $y$. If $v^-x\in E(G)$, then $P,P_v$ can be combined into one path $yPu_4x_vP_vv^-xu_3u_2u_1vP_vy_v$, a contradiction. So $yv^-\in E(G)$.

Note that $P, P_v$ can be replaced by $y_vP_vvu_1u_2u_3x$ (or $y_vP_vvu_1xu_3u_2$) and cyclic path $x_vPv^-yPu_4$, so $x, u_2, y_v$ have no neighbors on $x_vP_vv^-$ and $u_4Py$, or we can combine $P, P_v$ into one path.

If $x$ has no neighbors on $P_v$ and $u_4Py$ is not a $3$-path, let $P_1=y_vPv^+x_vP_vvu_1u_2u_3x$ and $P_2=u_4Py$; If $x$ has no neighbors on $P_v$ and $u_4Py$ is a $3$-path, let $P_1=y_vPx_vu_4Px$ and $P_2=u_5y$;  If $x$ has a neighbor on $P_v$, let $P_1=xu_3u_4Py$ and $P_2=y_vP_vv^+x_vP_vvu_1u_2$. Note that each of $x, x_v$ is adjacent to at least one weighty vertex in $P, P_v$, respectively. We replace $P, P_v$ with $P_1, P_2$ in the corresponding cases, and claim that there are fewer weighty vertices in the new cover.  In the first two cases, $x$ has one weighty neighbor on $P_1$ and $u_4$ or $u_5$ has none in $P_2$, and in the last case, $x$ has no weighty neighbors on $P_1$, and $u_2$ has at most one weighty neighbor on $P_2$.  Clearly, we do not add bad paths (1-, 3- or cyclic paths) to the cover.  To obtain a contradiction, we show below that we do not create new bad or annoying endpoints.

Only $x$ in the last case could be a bad endpoint described in (iv), and when it is, we must have $u_2g, xg^-\in E(G)$, where $P_v=x_vP_vg^-gv^-vv^+P_vy_v$;  but in this case, we can combine $P, P_v$ into one path $y_vP_vvu_1xu_3u_2gv^-yPu_4x_vP_vg^-$, a contradiction.

We also claim that no new annoying endpoints are added.  In the first case, $u_4$ cannot be, since it has only one neighbors on $P_2$, and if $x$ is one, then $u_2$ must be adjacent to a vertex in $u_5Py$, which is impossible.  In the second case, no vertex is an annoying endpoint as $P_2$ is a $2$-path. In the last case, $x$ cannot be as it has only one neighbor on $P_1$, and if $u_2$ is one, then $u_4$ should be light and be adjacent to a PE-vertex, but $u_4x_v\in E(G)$ and $x_v$ is not a PE-vertex in $P_2$.

(c2).  $P_w\not=P_v$, and $v^-, v^+$ are adjacent to $x_w, x$ or $y$.   If $xv^-\in E(G)$, then $P, P_v, P_w$ can be combined into two paths: $P_wx_wu_4Py$ and $x_vP_vv^-xu_3u_2u_1vP_vy_v$, a contradiction. So we may assume that $xv^-, xv^+\not\in E(G)$.  It follows, by symmetry, that $yv^+\in E(G)$. But again, $P, P_v, P_w$ can be combined into two paths:  $P_wx_wu_4Pyv^+P_vy_v$ and $x_vP_vvu_1u_2u_3x$, a contradiction.
\end{proof}

\section{Weights on paths}\label{counting}

We give an initial weight of $10$ to each path in $\P$.  By Lemma~\ref{no-triangle}, all paths in $\P$ are non-cyclic paths with order more than $1$. So we may think that each endpoint of the paths in $\P$ gets an initial weight of $5$. Here is the rule to transfer weights between (vertices on) paths:
\begin{quote}
{\bf Rule to transfer weights:} Each endpoint sends a weight of $2$ to the adjacent weighty or heavy vertex, and each PE-vertex transfers $1$ to the adjacent light vertex.
\end{quote}

For convenience, we let $w(P)$ be the final weight on a path or a segment $P$. For a path $P\in \P$, let $s_1(P), s_2(P), s_3(P)$ and $n_o(P)$ be the number of weighty and heavy vertices,  light vertices, neutral vertices, and PE-vertices, respectively.  Then
 \begin{equation}\label{weight}
  w(P)=2+2s_1(P)+s_2(P)-n_o(P).
  \end{equation}

\begin{definition}
Let $P=xu_1u_2\ldots u_ky\in \P$.  For each $1\le i\le j\le k-1$,
\begin{itemize}
\item a neutral vertex $u_i$ is {\em free} if there are neither heavy nor weighty vertices on $P$ between $u_i$ and an endpoint ($x$ or $y$);
\item $u_iPu_j$ is a {\em heavy segment} if both $u_i$ and $u_j$ are heavy or weighty and there is no neutral vertices on it;  (so a single heavy or weighty vertex is also a heavy segment)
\item $u_iPu_j$ is a {\em neutral segment} if $u_i, u_j$ are non-free neutral and there is no heavy or weighty vertices on it. (so a single neutral vertex is also a neutral segment)
\end{itemize}
\end{definition}

Note that a light vertex may be on a heavy or neutral segment.  By Corollary~\ref{neutral} and Lemma~\ref{no-consecutive}, there are at least one neutral vertices between any two heavy vertices, so a heavy segment with more than one vertices must contain at least one weighty vertex,  and contain at most three vertices, and when it contains three vertices, it must be a light vertex adjacent to two weighty vertices.  Let a {\em heavy pair} be a pair of vertices in a heavy segment that are both heavy or weighty.  So every heavy segment contains either $0$ or $1$ heavy pair.  Let $n_h(P)$ be the number of heavy pairs on $P\in \P$.  So $n_h(P)\le 4$ for each $P\in \P$.

Similarly, a pair of neutral vertices in a neutral segment that are consecutive or separated by a light vertex is called a {\em neutral pair}.  So a neutral segment with $s$ neutral vertices contains $s-1$ {\em neutral pairs}.  A heavy segment (and similarly, a neutral segment) is {\em maximal} if it is not contained in a larger heavy segment (neutral segment).

\begin{lem}\label{weight-path}
For a path $P\in \P$ with $w(P)>|V(P)|$, $$n_h(P)\ge n_o(P)+n_q(P)+n_r(P),$$ where $n_h(P), n_o(P), n_q(P), n_r(P)$ are the numbers of heavy pairs, PE-vertices, neutral pairs, and free neutral vertices on $P$, respectively.
\end{lem}

\begin{proof}
As above, assume that $P$ contains $a$ maximal heavy segments, then $P$ contains $a-1$ maximal neutral segments. It follows that $s_1(P)=n_h(P)+a$ and $s_3(P)=n_q(P)+a-1+n_r(P)$. By \eqref{weight},
\begin{align*}
w(P)&=2+s_1(P)+s_2(P)+(n_h(P)+s_3(P)-n_q(P)+1-n_r(P))-n_o(P)\\
&=|V(P)|+n_h(P)+1-(n_q(P)+n_r(P)+n_o(P)).
\end{align*}
It follows that if $w(P)>|V(P)|$ then $n_h(P)\ge n_q(P)+n_r(P)+n_o(P)$, as claimed.
\end{proof}

For convenience, we call the number $n_o(P)+n_q(P)+n_r(P)$ the {\em good number of $P$}, and in particular, it is called the {\em good number of the segment} if $P$ is a segment of a path.

\begin{lem}\label{ClaimA}
If for some $i>1$, $xu_i\in E(G)$ and $u_{i+1}$ is heavy (so $\{u_i, u_{i+1}\}$ is a heavy pair), then
 the good number of $xPu_i$ is at least $1$, with equality if and only if $i=4$ and $u_2$ is heavy.
 \end{lem}

\begin{proof}  First of all,  $xPu_{i-1}$ contains no neighbors of $y$ by Corollary~\ref{no-neighbor-of-y}, and   contains at most one heavy or light vertex by Lemma~\ref{paired-cycle}.  We may assume that the good number of $xPu_i$ is at most $1$.

Clearly, $i>2$, or $xu_1u_2$ is a net.  Also, $i\not=3$, or by Lemma~\ref{no-c}, both $u_1, u_2$ are neutral (and free), so the good number of $xPu_i$ is $2$.    So $i\ge 4$, and $xPu_{i-1}$ contains at least one heavy, weighty, or light vertices, or there are at least two free neutral vertices on $xPu_i$.

First assume that $xPu_{i-1}$ contains no weighty vertices. Then it must contain exactly one heavy or light vertex, by Lemma~\ref{paired-cycle}.  If it contains a light vertex, then all neutral vertices on $xPu_{i-1}$ are free, thus the good number is at least $i-1-1\ge 2$.  Therefore, it contains a heavy vertex.  If $u_1$ is heavy, then $u_2, \ldots, u_{i-1}$ are all neutral, so it contains $i-3$ distinct neutral pairs, namely, $\{u_2, u_3\}, \{u_3, u_4\}, \ldots, \{u_{i-2}, u_{i-1}\}$;  If $u_2$ is heavy, then $u_1$ is free and $\{u_3, u_4\}, \ldots, \{u_{i-2}, u_{i-1}\}$ are $i-4$ distinct neutral pairs; if $u_1, u_2$ are not heavy, then $u_1, u_2$ are free neutral vertices.   So in either case, the good number is at least $i-3$.  Then $i=4$ and $u_1$ or $u_2$ is heavy.  By Lemma~\ref{no-7}, $u_1$ cannot be heavy, so $u_2$ is heavy.

Now assume that $xPu_{i-1}$ contains a weighty vertex, say $u_j$ for some $1<j<i$.  Then $xu_j\in E(G)$. If $j=2$, then $u_1u_3\in E(G)$, or we will have a net.  Note that $u_4\not=u_i$ (otherwise $u_4u_5$ is a cut-edge),  $u_4$ cannot be neutral (otherwise, $\{u_3,u_4\}$ is a neutral pair and $u_1$ is free, so the good number of $xPu_i$ is at least $2$), and $u_4$ cannot be light  (otherwise, $u_5$ must be neutral by Corollary~\ref{neutral-end}, thus $\{u_3, u_5\}$ is a neutral pair and $u_1$ is free, so the good number of $xPu_i$ is at least $2$).  So $u_4$ is heavy.  Now $u_5$ is neutral and $u_6$ must be $u_i$, or $\{u_5, u_6\}$ is a neutral pair.  But then by Lemma~\ref{no-two-consecutive}, $u_5$ must be adjacent to some vertex on $xPu_i$ other than $u_4,u_6$, which is impossible.

So  $j\ge 3$,  and one vertex on $xPu_{j-1}$ must be heavy or light (otherwise there are at least two free neutral vertices).   As $xPu_{j-1}$ contains no weighty vertices,  the above argument shows that $xPu_{j-1}$ has good number at least $2$, unless $j=4$ and $u_2$ is heavy.  In the bad case, $i=j+2=6$ (for otherwise $\{u_{j+1}, u_{j+2}\}$ is a neutral pair), and by Lemma~\ref{no-two-consecutive}, $u_1, u_3, u_5$ must be adjacent only to vertices on $xPu_6$, which is impossible.
\end{proof}

\begin{lem}\label{heavy-triple}
Let $P=xu_1\ldots u_ky\in \P$. If for some $1<i<k$, $xu_i, yu_{i+2}\in E(G)$ and $u_{i+1}$ is light, then $w(P)\le |V(P)|$.
\end{lem}

\begin{proof}
Assume that $w(P)>|V(P)|$. Then by Lemma~\ref{weight-path}, $n_h(P)\ge n_o(P)+n_q(P)+n_r(P)$.

By Lemma~\ref{paired-cycle}, $xPu_i$ and $yPu_{i+2}$ contain at most one heavy vertex altogether.  By Corollary~\ref{no-neighbor-of-y}, $xPu_i$ contains no neighbors of $y$ and $u_{i+1}Py$ contains no neighbor of $x$. We may assume that $yPu_{i+2}$ contains no heavy vertices.   As $i+2\not=k-1$ (otherwise $u_{i+2}u_ky$ is a net),  $yPu_{i+2}$ contains at least one free neutral vertex, so the good number of $yPu_{i+2}$ is at least one.

If $xPu_i$ contains no heavy vertices, then similarly the good number of $xPu_i$ is also at least one, so the good number of $P$ is at least $2$,  but $P$ has only one heavy pair, a contradiction.  Thus,  we may assume that $xPu_i$ contains exactly one heavy vertex.

If $xPu_i$ contain no heavy pairs, then its good number must be zero. It follows that $u_1$ is heavy (otherwise $n_r\ge 1$), $xu_3\in E(G)$ (otherwise $n_q\ge 1$), and $i\ge 3$.  As $u_2$ cannot be a PE-vertex (otherwise $n_o+n_r+n_q\ge 2$ but $n_h=1$), $u_2u_a\in E(G)$ for some $a\not=1,3$. By Lemma~\ref{no-two-consecutive}, $i>a$.    By Lemma~\ref{chord} (b), $u_{a-1}$ is neutral, so $n_q\ge 1$ thus $n_q+n_r\ge 2$, a contradiction.

Thus,  we may assume that $xPu_i$ contains a heavy pair, that is, $xu_j\in E(G)$ and $u_{j+1}$ is heavy for some $2\le j<i-1$. By Lemma~\ref{ClaimA}, the good number of $xPu_j$ is at least $1$.  Thus it must be exactly $1$, $j=4$ and $u_2$ is heavy. But then $xPu_i$ contains two heavy vertices, a contradiction.
\end{proof}

\begin{lem}\label{main-lemma}
For each $P\in \P$, $w(P)\le |V(P)|$.
\end{lem}

\begin{proof}
Let $P=xu_1u_2\ldots u_ky\in \P$. By Lemma~\ref{no-7}, $P$ is non-cyclic and is not a $1$-path or a $3$-path.  Assume that $w(P)>|V(P)|$.  Let $n_h, n_o, n_q, n_r$, as defined in the Lemma~\ref{weight-path},  be the numbers of heavy pairs,  PE-vertices, neutral pairs, and free neutral vertices on $P$, respectively. By Lemma~\ref{weight-path},
\begin{equation}
n_o+n_q+n_r\le n_h\le 4.
\end{equation}

By Lemma~\ref{heavy-triple} and Lemma~\ref{no-consecutive}, we may assume that each heavy pair consists of two consecutive vertices on $P$, at least one of which is a weighty vertex.

\smallskip

{\bf Case 1.} $P$ contains a heavy pair consisting of two weighty vertices. Assume that $xu_i, yu_{i+1}\in E(G)$ for some $1<i<k-1$.  Note that by Lemma~\ref{no-two-consecutive}, $xu_{i-1}, yu_{i+2}\not\in E(G)$.

{\bf Case 1.1.} $P$ contains at least two heavy pairs.

First assume that $P$ contains another heavy pair consisting of two weighty vertices, say $\{u_j, u_{j+1}\}$ with $xu_j, yu_{j+1}\in E(G)$ for some $j>i$.  In this case, there are no other heavy pairs.  So $n_h=2$.   As $P$ can be rerouted so that $u_1$ and $u_k$ are the endpoints,   $u_1, u_k$ must be neutral by Corollary~\ref{neutral-end}, thus free, so $n_r=2$ and $n_o=n_q=0$.   Then $u_{j-1}$ is not in a neutral pair. It follows that $u_{j-2}$ is heavy or $u_{j-2}=u_{i+1}$, and in either case, $u_{j-1}u_s\in E(G)$ for some $s\not=j-2, j$, or $u_{j-1}$ is a PE-vertex (a contradiction to $n_o=0$).  By Lemma~\ref{chord}, $u_{s+1}$ (if $s<j$) or $u_{s-1}$ (if $s>j$) is neutral, so we have a neutral pair, a contradiction to $n_q=0$.

Now we assume that $\{u_i, u_{i+1}\}$ is the only heavy pair containing two weighty vertices. Note that if a heavy pair is $\{u_s, u_{s+1}\}$ such that $xu_s\in E(G)$ and $u_{s+1}$ is heavy, then by Corollary~\ref{no-neighbor-of-y}, $s<i$.   Similarly for such a heavy pair involving $y$.  Also note that $n_h\le 3$.

Consider the case $n_h=3$.    Let $\{u_s, u_{s+1}\}$ and $\{u_t, u_{t-1}\}$ be the other two heavy pairs such that $s<i, t>i+1$, $xu_s, yu_t\in E(G)$, and $u_{s+1}, u_{t-1}$ are heavy.  By Lemma~\ref{paired-cycle}, $P$ contains no other heavy or light vertices.  Now by Lemma~\ref{ClaimA},  each of $xPu_i$ and $u_{t+1}Py$ has the good number at least two, thus the good number of $P$ is at least $4$, a contradiction.

Now let $n_h=2$ and $\{u_s, u_{s+1}\}$ be the only other heavy pair such that $xu_s\in E(G)$ and $u_{s+1}$ is heavy.  By Lemma~\ref{ClaimA}, $xPu_s$ has the good number at least $2$ or $s=4$ such that $u_2$ is heavy.  In the latter case, $u_{i+1}Py$ contains no heavy or light vertices by Lemma~\ref{paired-cycle}, so has at least two free neutral vertices, thus the good number of $P$ is at least $3$, a contradiction.  For the former case, the good number of $u_{i+1}Py$ is $0$. It follows that $u_k$ must be heavy, and by Lemma~\ref{paired-cycle}, there are no other heavy or light vertices on $P$ other than $u_{s+1}$ and $u_k$.  Then $s=3$ and $i=6$.  Now $u_{i-1}$ must be adjacent $u_t$ for some $t\not=i-2, i$.  Clearly, $t\not=1,2, i+2$.  Then $t>i+1$, and by Corollary~\ref{neutral},  $u_{t-1}$ is neutral, so $\{u_{t-1}, u_t\}$ is a neutral pair, a contradiction to the fact that the good number of $u_{i+1}Py$ is $0$.

{\bf Case 1.2.} $\{u_i, u_{i+1}\}$ is the only heavy pair on $P$.  Then the good number of $P$ is at most one.  By symmetry, we may assume that the good number of $xPu_i$ is at most one and the good number of $u_{i+1}Py$ is $0$.  It follows that $u_k$ cannot be neutral (otherwise it is free).

Let $xu_j\in E(G)$ for some $j>i$.  Then $P$ can be rerouted so that $u_1$ is an endpoint.  By Lemma~\ref{neutral-end}, $u_1$ is neutral (and free).  So $n_r\ge 1$. It follows that $n_r=1$ and $n_o=n_q=0$.  By Lemma~\ref{no-two-consecutive}, $u_{j-1}u_s\in E(G)$ for some $s\not=j-2, j$.  By Corollary~\ref{neutral}, $u_{s+1}$ (if $s<j$) or $u_{s-1}$ (if $s>j$) is neutral, thus $n_q\ge 1$, a contradiction. It follows that $u_{i+1}Py$ contains no neighbor of $x$, and by symmetry, $xPu_i$ contains no neighbour of $y$.

Now that $u_k$ cannot be neutral or weighty, it must be light or heavy.  But if it is light, then $u_{k-1}$ cannot be a neighbour of $y$ (otherwise $yu_ku_{k-1}$ is a net), or heavy by Lemma~\ref{no-consecutive}, so $u_{k-1}$ is neutral, thus the good number of $u_{i+1}Py$ is not $0$, a contradiction.  So we assume that $u_k$ is heavy.

Observe that $u_{k-1}$ is neutral.   We may assume that $u_{k-2}$ is not neutral, or we have a neutral pair $\{u_{k-2}, u_{k-1}\}$ on $u_{i+1}Py$, a contradiction.  So $u_{k-2}$ is heavy, light or $yu_{k-2}\in E(G)$.

Note that $u_{k-2}$ cannot be heavy.  Suppose otherwise. By Lemma~\ref{paired-cycle}, $xPu_i$ contains no heavy or light vertices.   So $u_1, u_2$ are free neutral vertices. It follows that $n_r\ge 2$, a contradiction.

We also have $u_{k-2}y\not\in E(G)$. Suppose otherwise. Then $u_{k-1}u_s\in E(G)$ for some $i+1<s<k-2$, or $u_{k-1}$ is a PE-vertex.    By Lemma~\ref{chord}, $u_{s+1}$ is neutral, thus $\{u_s, u_{s+1}\}$ is a neutral pair on $u_{i+1}Py$, a contradiction.

So let $u_{k-2}$ be light.  By Lemma~\ref{no-consecutive},  $u_{k-3}$ is not heavy or light.  But $u_{k-3}$ is not a neighbour of $x$ or $y$, so $u_{k-3}$ must be neutral.  Now $\{u_{k-3}, u_{k-1}\}$ is a neutral pair, a contradiction to the assumption that the good number of $u_{i+1}Py$ is $0$.

\smallskip

{\bf Case 2.}  $P$ contains no heavy pairs consisting of only weighty vertices.

{\bf Case 2.1.} $n_h=0$. It follows that $n_o=n_q=n_r=0$.  Recall that $k>1$, by Lemma~\ref{no-triangle}.

Assume first that $P$ contains no weighty vertices.  Then $u_1, u_k$ are heavy, and the vertices on $u_1Pu_k$ are alternatively heavy and neutral.  Let $v\not=u_1, u_3$ be the third neighbor of $u_2$. Then $v=u_t\in P$ for some $t>3$, or $u_2$ is a PE-vertex (this contradicts to the fact that $n_o=0$).  But $u_{t-1}$ and $u_{t+1}$ are heavy. So  by Lemma~\ref{chord} (a), $u_1,u_{t-1}$ are adjacent to one endpoint of a path $Q\not=P$ and $u_3, u_{t+1}$ are adjacent to the other endpoint of $Q$.  Note that $t\not=4$, or $u_2u_3u_4$ is a net.   Now $u_4$ is neutral and must be adjacent to $v'\not\in P$ or $u_s$ for some $s>5$. In the former case, $u_{i+3}$ is a PE-vertex, and in the latter case,  $u_{s-1}$ or $u_{s+1}$  cannot be heavy by Lemma~\ref{chord} (a), a contradiction.

Now let $xu_i\in E(G)$ for some $i>1$, and we may assume that $xu_j\not\in E(G)$ for $1<j<i$.  First let $i>2$.   Then  $u_{i-2}$ cannot be neutral (or $\{u_{i-2}, u_{i-1}\}$ is a neutral pair) or light (otherwise, $u_{i-1}$ is free if $i=3$, or $u_{i-3}$ must be neutral thus $\{u_{i-3}, u_{i-1}\}$ is a neutral pair).  So $u_{i-2}$ is heavy or $yu_{i-2}\in E(G)$.  Now $u_{i-1}$ must be adjacent to $u_t$ for some $t\not=i-3,i-1$, or it is a PE-vertex.  By Lemma~\ref{chord} (b), $u_{t-1}$ (if $t>i-1$) or $u_{t+1}$ (if $t<i-3$) is neutral, thus $u_t$ is in a neutral pair, a contradiction to $n_q=0$.  Now let $i=2$.  Then $u_1u_3\in E(G)$, or $xu_1u_2$ is a net.  So $xu_j\in E(G)$ for some $j>3$, or $u_1$ is a better endpoint of $P$ than $x$.  Clearly $j\not=4$, or $u_4u_5$ is a cut-edge.  So $u_{j-2}$ must be heavy or adjacent to $y$. Now a similar argument as above shows $n_q>0$, a contradiction.

{\bf Case 2.2.}  $n_h=1$.  Let $\{u_i, u_{i+1}\}$ be the only heavy pair with $xu_i\in E(G)$ for some $1<i<k$  and $u_{i+1}$ is heavy.   As the good number of $xPu_i$ is at most $1$,  by Lemma~\ref{ClaimA},  $i=4$ and $u_2$ is  heavy.  So $u_1$ is free, and $n_q=n_o=0$.

Now,  $u_3u_t$ for some $t\not=2,4$, or $u_3$ is a PE-vertex, a contradiction to $n_o=0$.  Clearly, $t\not=1$, so $t\ge 6$. By Lemma~\ref{neutral-end}, $u_{t-1}$ is neutral or $xu_{t-1}\in E(G)$. In the former case, we have a neutral pair, thus $n_q>0$, a contradiction. As $y$ has no neighbors on $xu_1u_2u_3$, Lemma~\ref{no-two-consecutive} implies that the latter case cannot happen.

{\bf Case 2.3.}  $n_h=2$.  Let $\{u_i, u_{i+1}\}$ and $\{u_{t-1}, u_t\}$ be the two heavy pairs for some $i<t-1$.

First assume that $xu_i, xu_{t-1}\in E(G)$ and $u_{i+1}, u_t$ are both heavy.  By Lemma~\ref{paired-cycle}, $u_{i+1},u_t$ are adjacent to the same endpoint $x'\in P'\in \P$, and they are the only heavy/light vertices on $xPu_t$. As $i\ge 3$ (otherwise there is a net) and $u_1, u_2, \ldots, u_{i-1}$ are free neutral vertices, $n_r\ge 2$. It follows that $n_r=2$ and $i=3$, and $n_o=n_q=0$.  By Lemma~\ref{no-two-consecutive}, $u_2$ can only be adjacent to vertices on $P$, thus $u_2u_a\in E(G)$ for some $a\ge 4$, and by Lemma~\ref{chord}, $u_{a-1}$ is neutral, so $n_q\ge 1$, a contradiction.

Note that if $xu_{t-1}, yu_{i+1}\in E(G)$ and $u_t, u_i$ are heavy, then $P$ can be rerouted so that $u_i$ and $u_t$ are endpoints, a contradiction to Lemma~\ref{neutral-end}.  Thus, we assume that $1<i<t<k$, $xu_i, yu_t\in E(G)$ and $u_{i+1}, u_{t-1}$ are heavy, and $y$ has no neighbors on $xPu_i$ and $x$ has no neighbors on $u_tPy$.  Let $u_{i+1}$ be adjacent to an endpoint $x'\in P'\in \P-\{P\}$.

By Lemma~\ref{ClaimA},  $xPu_{i-1}$ and $u_{t+1}Py$ both have the good number at least $1$, thus $i=4, t=k-3$ and $u_2$ and $u_{k-1}$ are heavy.  So there are two free neutral vertices, and $n_q=n_o=0$.   Note that $i+1<t-1$.  For otherwise, by Lemma~\ref{paired-cycle},  $xPu_i$ and $u_tPy$ contain at most one heavy/light vertex altogether, a contradiction.

Now, $u_3u_t$ for some $t\not=2,4$, or $u_3$ is a PE-vertex.  Clearly, $t\not=1$, so $t\ge 6$. By Lemma~\ref{neutral-end}, $u_{t-1}$ is neutral or $xu_{t-1}\in E(G)$. In the former case, we have a neutral pair, a contradiction. As $y$ has no neighbors on $xu_1u_2u_3$, Lemma~\ref{no-two-consecutive} implies that the latter case cannot happen.

{\bf Case 2.4.}  $n_h\in \{3,4\}$.  As in Case 2.3,   we may assume that the neighbors of $x$ are $u_1, u_i, u_j$ and the neighbor of $y$ are $u_s, u_t, u_k$ with $1<i<j<s\le t<k$ such that $u_{i+1}, u_{j+1}, u_{s-1}, u_{t-1}$ are all heavy.

By Lemma~\ref{paired-cycle}, $u_{i+1}, u_{j+1}$ are adjacent to the same endpoint of a path in $\P$, and there are no other heavy or light vertices on $xPu_j$. Note that $i\ge 3$ (otherwise $xu_1u_2$ is a net), so $xPu_i$ contains at least $i-1\ge 2$ free neutral vertices, i.e., $u_1, u_2,\ldots, u_{i-1}$.  Similarly, $u_sPy$ contains at least $k-t\ge 2$ free neutral vertices when $n_h=4$ (that is, $s<t$). Note that when $n_h=3$ (that is, $s=t$), the good number of $u_sPy$ is $1$, thus by Lemma~\ref{ClaimA}, $s=k-3$, $u_{k-1}$ is heavy and $u_k$ is free.  So $P$ contains $n_h$ free neutral vertices. It follows that $n_q=n_o=0$, and $i=3$ and $j=6$.    By Lemma~\ref{no-two-consecutive},  $u_5$ must be adjacent to $u_1$ or $u_2$,  but then $P, P'$ can be combined into one path: $P'x'u_4u_5u_1u_2u_3xu_6Py$ if $u_5u_1\in E(G)$, and $P'x'u_4u_3xu_1u_2u_5Py$ if $u_5u_2\in E(G)$, a contradiction.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{main}:]
Consider an optimal path cover $\P$ of $G$, and assign a weight of $10$ to each path in $\P$.  By Lemma~\ref{main-lemma}, the total weight is $10|\P|=\sum_{P\in \P} w(P)\le \sum_{P\in \P} |V(P)|=n$.  So $|\P|\le n/10$, that is, $G$ has a path cover with at most $n/10$ paths.
\end{proof}

{\bf Acknowledgement:} The author would like to thank the referees for their valuable comments, which helped to simplify the proof and improve the presentation of the paper significantly.


TITLE: smallest root of $f$ is strictly less than smallest root of $g$.
QUESTION [3 upvotes]: I have two polynomials, namely, $$f(y)=y^3-(k+3)y^2+2(k+1)y-2,$$ $$g(y)=y^2-(k+2)y+2.$$ where $k\ge4$ is a natural number. I want to prove that smallest root of $f$ is strictly less than smallest root of $g$.
I thought of calculating roots of $f$ and $g$ explicitly but that calculation is not very easy for $f$.
Next approach is: I already know that all roots of $f$ and $g$ are positive. We have smallest root of $g$ as $\lambda=\frac{(k+2)-\sqrt{(k+2)^2-8}}{2}$. We know that $f(0)<0$. So if we can prove that $f(y)>0$ for some $y \in (0,\lambda]$. Then we are done.
Now
$f(y)=y(g(y)+2k-y)-2.$
So, $f(\lambda)=\lambda(2k-\lambda)-2$. But I am not sure that $f(\lambda)>0$.
How to prove the result?

REPLY [2 votes]: Note that $$f(y) = (y-1)g(y) + (k-2)y$$ so if $g(y)=0$ then $f(y) = (k-2)y$. Since for $k>2$ both roots of $g$ are positive it follows that $f(y) > 0$.


TITLE: How to simplify $\tan{\arcsin{\frac{y}{R}}/2}$?
QUESTION [5 upvotes]: I have verified with Mathematica that, for $R>0, y \in \mathbb{R}$:
$$ \tan{\frac{\arcsin{\frac{y}{R}}}{2}} = \frac{R - \sqrt{R^2 -y ^2}}{y}$$
using
Assuming[Element[y, Reals] && R > 0,
 FullSimplify[TrigToExp[Tan[ArcSin[y/R]/2]]]]

How can I prove this withouse messing with complex exponentials and logarithms?

REPLY [1 votes]: Let  $\displaystyle\arcsin\frac yr=\phi\implies \sin\phi=\frac yR\ \ \ \ (1)$
and based on the definition of principal value, $\displaystyle-\frac\pi2\le\phi\le\frac\pi2\ \ \ \  (2)$
So, we need to find $\displaystyle\tan\frac\phi2$
Using Weierstrass substitution, $\displaystyle\sin\phi=\frac{2\tan\frac\phi2}{1+\tan^2\frac\phi2}$
So, using  $\displaystyle(1),\frac{2\tan\frac\phi2}{1+\tan^2\frac\phi2}=\frac yR\implies y\tan^2\frac\phi2-2R\tan\frac\phi2+y=0\  \ \ \ (3)$
Solving the Quadratic Equation for $\displaystyle\tan\frac\phi2=\frac{R\pm\sqrt{R^2-y^2}}y$
Now using $\displaystyle(2), -\frac\pi4\le\frac\phi2\le\frac\pi4\implies -1\le\tan\frac\phi2\le1$
Observe that for real $\displaystyle\phi, R^2\ge y^2\implies R\ge |y|$ as $R>0$
If $\displaystyle R=|y|,\tan\frac\phi2=\pm1$ where both roots are same
Else  $\displaystyle\frac{R+\sqrt{R^2-y^2}}{|y|}> \frac R{|y|}>1,$ hence  should be discarded.

Observe that if $\displaystyle\tan\frac{\phi_1}2,\tan\frac{\phi_2}2$ are the roots of $(3),$
using Vieta's formula, $\displaystyle\tan\frac{\phi_1}2\tan\frac{\phi_2}2=1$
$\displaystyle\implies\tan\frac{\phi_1}2=\frac1{\tan\frac{\phi_2}2}=\cot\frac{\phi_2}2=\tan\left(\frac\pi2-\frac{\phi_2}2\right)=\tan\frac{\pi-\phi_2}2$
$\displaystyle\implies\frac{\phi_1}2=\frac{\pi-\phi_2}2\iff\phi_1=\pi-\phi_2 $
$\displaystyle\implies\sin\phi_1=\sin\left(\pi-\phi_2\right)=\sin\phi_2 $
Also,  $\displaystyle\sin\phi=\frac{2\tan\frac\phi2}{1+\tan^2\frac\phi2}=\frac{2\cot\frac\phi2}{1+\cot^2\frac\phi2}$ (multiplying the numerator & the denominator by $\displaystyle\cot^2\frac\phi2$)


TITLE: $2^n-1$ divides $2^{(m-1)!}-1$ if $n$ divides $(m-1)!$
QUESTION [0 upvotes]: Suppose $m$ is an even positive integer and $n\in\mathbb{N}$ divides $(m-1)!$. It is said that then $2^n -1$ divides $2^{(m-1)!} - 1$. I expect this claim to be easy provable because there is no comment in my book. Still, I couldn't show it. Can you give me a hint please?

REPLY [0 votes]: We have $(m-1)!=nk$ for some $k$ therefore $2^{(m-1)!}-1=2^{nk}-1=(2^{n})^k-1=(2^n - 1)((2^{n})^{k-1} + (2^{n})^{k-2} + .. + 1)$
I used the identity $a^n - b^n =(a-b)(a^{n-1} + a^{n-2}b + .. + b^{n-1})$


TITLE: What does it mean when $|z| = 2$ is the curve in a contour integral?
QUESTION [1 upvotes]: B) Evaluate:
$$\oint_{|z|=2} \tan{z}\,dz$$
Specifically looking at B on the image. What is meant by $|z|=2$?

REPLY [2 votes]: $|z| = 2$ is the circle of radius $2$ centered at the origin. Typically, when one writes an integral like
\begin{align}
\oint_{|z| = r} f(z) \, dz,
\end{align}
what is meant is that we have to consider the path $\gamma: [0,2\pi] \to \Bbb{C}$ given as $\gamma(t) := re^{it}$ (so the orientation of the path is counter clockwise). And then, really we're supposed to compute a line integral:
\begin{align}
\int_{\gamma} f(z) \, dz &= \int_0^{2\pi} f(\gamma(t)) \cdot \gamma'(t) \, dt \\
&= \int_0^{2\pi} f(r e^{it}) \cdot ir e^{it} \, dt.
\end{align}


TITLE: About holomorph of a finite group being the normalizer of regular image
QUESTION [2 upvotes]: Here is part of Exercise 5.5.19 in Dummit & Foote's Abstract Algebra:

Let $H$ be a group of order $n$, let $K=\operatorname{Aut}(H)$ and $G=\operatorname{Hol}(H)=H\rtimes K$ (where $\varphi$ is the identity homomorphism). Let $G$ act by left multiplication on the left cosets of $K$ in $G$ and let $\pi$ be the associated permutation representation $\pi:G\to S_n$.
(a) Prove the elements of $H$ are coset representatives for the left cosets of $K$ in $G$ and with this choice of coset representatives $\pi$ restricted to $H$ is the regular representation of $H$.
(b) Prove $\pi(G)$ is the normalizer in $S_n$ of $\pi(H)$.
Deduce that under the regular representation of any finite group $H$ of order $n$, the normalizer in $S_n$ of the image of $H$ is isomorphic to $\operatorname{Hol}(H)$. [Show $|G|=|N_{S_n}(\pi(H))|$.]

I could easily show (a), but even before attempting to prove part (b), I was puzzled: Does it imply that $\pi$ is injective? The restriction of $\pi$ to $H$ is injective by part (a), but I don't think $\pi$ is injective in general.
For example, $D_8\simeq\operatorname{Aut}(D_8)$, so if $H=D_8$, then $K$ is a normal subgroup of $G$ (being of index 2), so $ker\pi=K\neq1$.
Am I wrong somewhere in my deduction?

REPLY [1 votes]: In the case of $H=D_8$, it's not true $K$ is index $2$; actually $K$ is index $|H|$ in $G=H\rtimes K$. And $K$ is never normal in $G$, unless it's trivial of course.
The best way to think about $G$ is as an "affine group" of $H$. Indeed, if $H=\mathbb{Z}_p^n$ then $G$ is literally the affine group of $H$ as a vector space. In general, we can think of $G$ as the subset of $S_H$ comprised of "affine functions" of the form $x\mapsto \alpha(x)b$ where $\alpha\in\mathrm{Aut}(H)$ and $b\in H$.
Conjugating $K$ by $H$ yields functions of the form $\alpha(xb^{-1})b=\alpha(x)\alpha(b)^{-1}b$; to be an automorphism of $H$ (element of $K$) it must preserve $e\in H$ as a function, which requires $\alpha(b)=b$ (which, conversely, is sufficient), and this is only true for all $b$ if $\alpha$ is the identity automorphism. On the other hand, conjugating $H$ by $K$ yields functions $\alpha(\alpha^{-1}(x)b)=x\alpha(b)$, which are still elements of $H$, so $H$ is normal in $G$.
Note $H$ is a transversal for $G/K$, and indeed $G$ acts on $H$ representing $G/K$ matches $G$ acting on $H$ by affine functions in the way I described above. You want to show $N_{S_H}(H)=G$ here.


TITLE: Is an assumption a necessary or sufficient condition?
QUESTION [0 upvotes]: In mathematics and logics, is an assumption for a statement/claim a necessary or sufficient condition for the statement/claim?
From my past experience with mathematics, an assumption may be neither. But in logical questions in GRE, GMAT and LSAT exams, an assumption seems to mean a necessary condition.
Thanks!

REPLY [2 votes]: The question is a bit vague and it's quite possible the standardized test writers don't know any formal logic.  I hope the following discussion will clear things up.
Claim: Assume $P$. Then $Q$.
Here the meaning of the claim is precisely that the assumption $P$ is sufficient for the conclusion $Q$.  It may or may not be necessary.
However, note that there can be multiple assumptions:
Claim: Assume that $x$ is even and assume that $x$ is prime.  Then $x < 10$.
Here there are two assumptions, "$x$ is even" and "$x$ is prime", neither of which alone is necessary or sufficient for the conclusion $x < 10$.  However, note that the conjunction of the two assumptions is sufficient for the conclusion.  In general, if we package all of our assumptions into a single assumption (a conjunction of several sentences, perhaps) then this assumption is understood to be sufficient for the conclusion that follows.

EDIT: When working with sufficiently powerful theories, we very rarely know for certain that our assumptions are necessary for our conclusions, even if we think they are.  For example, if $\mathsf{ZFC}$ turned out to be inconsistent, then all of the assumptions anyone has ever made in $\mathsf{ZFC}$ theorems (beyond the $\mathsf{ZFC}$ axioms themselves, which are implicitly assumed) would be unnecessary.


text:
\begin{document}
\maketitle

\begin{abstract}
In this Note, we describe the stationary equilibria and the
asymptotic behaviour of an heterogeneous logistic reaction-diffusion
equation under the influence of autonomous or time-periodic forcing
terms. We show that the study of the asymptotic behaviour in the
time-periodic forcing case can be reduced to the autonomous one, the
last one being described in function of the ``size" of the external
perturbation. Our results can be interpreted in terms of maximal
sustainable yields from populations. We briefly discuss this last
aspect through a numerical computation.

\vspace{2ex}

\noindent{\bf R\'esum\'e:} {\bf Analyse de mod\`eles de dynamique de
populations sous l'influence de perturbations externes. } Cette Note
a pour objet l'\'etude des \'etats stationnaires et du comportement
asymptotique d'\'equations de r\'eaction-diffusion avec coefficients
h\'et\'erog\`enes en espace, auxquelles nous ajoutons un terme de
perturbation stationnaire ou p\'eriodique en temps. Nos r\'esultats
peuvent s'interpreter en termes de r\'ecolte maximale supportable
par une population. Nous soulignons cet aspect \`a l'aide d'un
calcul num\'erique.

\end{abstract}

\section{Introduction}\label{sec1}

The purpose of this Note is to study the following model:
\be\label{eq_evo} u_t= \nabla \cdot(A(x) \nabla u)+u(\mu(x)-\nu(x)
u)- f(\omega t,x)\rho_{\varepsilon}(u), \ (t,x) \ \in \
\R_+\times\Omega. \ee The reaction-diffusion models of the type
$u_t= \nabla \cdot(A(x) \nabla u)+u(\mu(x)-\nu(x) u)$ correspond to
the natural extension of the classical Fisher model \cite{fi}. They
were first introduced by Shigesada et al. \cite{skt} for population
dynamics. Our aim is to understand the asymptotic behaviour of the
solutions of such models, when we add a time-periodic forcing term
$f(\omega t,x)$. With such additional term, this can interpreted as
an \emph{harvesting model} with seasonal harvesting. In real-life
context this
 perturbation term can arise when a quota is set on the harvesters.

We make the following assumptions on the coefficients: the diffusion
matrix $A(x)$ is assumed to be of class $C^{1,\alpha}$ (with
$\alpha>0$) and uniformly elliptic; i.e. there exists $\tau>0$ such
that $A(x)\ge\tau I_N$ for all $x\in\Omega$. The functions $\mu$ and
$\nu$ belong to $L^{\infty}(\Omega)$. Moreover, we assume that there
exist $\underline{\nu}$ and $\overline{\nu}$ such that
$0<\underline{\nu}<\nu(x)<\overline{\nu}$ for all $x$ in $\Omega$.
The function $f$ is 1-periodic in the first variable and belongs to
$C^0(\R\times\Omega)$, and the function $\rho_{\varepsilon}$ defines
a ``regularized threshold'': it is a $C^1(\R)$ nondecreasing
function such that $\rho_{\varepsilon}(s)=0$ for all $s\leq 0$ and
$\rho_{\varepsilon}(s)=1$ for all $s\geq \varepsilon$. This
threshold guarantees the non-negativity of the solutions of
(\ref{eq_evo}).

Two kinds of domains $\Omega$ are considered: either $\Omega=\R^N$
or $\Omega$ is a smooth bounded domain of $\R^N$. We qualify the
first case, $\Omega=\R^N$,  as the {\em sp-case} and the second one
as the {\em bounded case}. Indeed, in the sp-case, we assume that
$A(x)$, $\mu(x)$, $\nu(x)$ and $f(s,x)$ depend on the variables
$x=(x_1,\cdots,x_N)$ in a space-periodic fashion (i.e. for
$L_1,\ldots,L_N$ fixed positive numbers, a function $g$ is said to
be sp-periodic if $g(x+k)=g(x)$ for all $x\in\mathbb{R}^N$ and $k\in
L_1\mathbb{Z}\times\cdots\times L_N\mathbb{Z}$). In the bounded
case, throughout this paper, we assume that we have Neumann boundary
conditions on $\partial \Omega$.

\section{The case of autonomous forcing}\label{sec2}
All the results of this section remain true either in the {\bf
sp-periodic} or {\bf bounded cases}. The proofs are detailed in
\cite{rc}.

We consider the equation (\ref{eq_evo}) with $f(wt,x)=\delta h(x)$,
i.e. \be\label{eq_evo2} u_t= \nabla \cdot(A(x) \nabla
u)+u(\mu(x)-\nu(x) u)-\delta h(x)\rho_{\varepsilon}(u), \ (t,x) \
\in \ \R_+\times\Omega, \ee where $h$ is a continuous function such
that there exist $\alpha,\beta>0$ with $\alpha< h(x)<\beta \hbox{
for all }x \in \Omega$, and which is sp-periodic in the sp-case.

Let $\lambda_{1}$ be defined as the unique real number such that
there exists a function $\phi>0$ which satisfies
\be\label{eqlambda1} -\nabla \cdot(A(x) \nabla
\phi)-\mu(x)\phi=\lambda_{1}\phi\hbox{ in }\Omega, \phi>0 \hbox{ and
 }\|\phi\|_{\infty}=1, \ee with either periodic or Neumann boundary
conditions, depending on $\Omega$, as mentioned above. The function
$\phi$ is uniquely defined by (\ref{eqlambda1}) (the existence and
uniqueness of $\lambda_1$ and $\phi$ follow from the standard
Krein-Rutman theory).

\vspace{1ex}
\begin{a2remark} \label{rem1}{\rm Note that if we assume that $\lambda_1<0$ and $\delta=0$, then, given any
continuous and bounded function $u_0$, the solution $u(t,x)$ of
(\ref{eq_evo2}) with initial data $u_0$ converges to a function $p$
which is the unique bounded and positive  solution of $\nabla
\cdot(A(x) \nabla p)+p(\mu(x)-\nu(x) p)=0$, $x \in\Omega$. These
convergence,  as well as existence and uniqueness results are proved
in \cite{bhr1}.}
\end{a2remark}
\vspace{1ex}

We first describe the steady states of (\ref{eq_evo2}) without
``regularized threshold'': \be\label{eq_sta} \nabla \cdot(A(x)
\nabla p_{\delta})+p_{\delta}(\mu(x)-\nu(x) p_{\delta})-\delta
h(x)=0, \ x \ \in \ \Omega.\ee Using a Leray-Schauder degree
argument, together with the uniqueness of the solution $p$ defined
in the above remark, we prove the following\hfill\break

\begin{a2theorem}
\label{CRASth1} There exists $\delta^*>0$ such that for all $\delta$
s. t. $0<\delta<\delta^*$, {\rm(\ref{eq_sta})} admits  two distinct
positive solutions, $p^1_\delta$ and $p^2_\delta$. Moreover,
$p^1_\delta\to 0$ and $p^2_\delta\to p$ uniformly in $\Omega$ as
$\delta\to 0$.
\end{a2theorem}

\vspace{1ex}

Let us set $\ds{\underline{\phi}:=\min_{x\in \Omega}\phi(x)},$  $
\delta_1:=\ds{\frac{\lambda_1^2 \underline{\phi}}{\beta
\overline{\nu}(1+\underline{\phi})^2}}$ and
 $\delta_2:=\ds{\frac{\lambda_1^2 }{4 \alpha \underline{\nu}}}.$
 Then we have the following theorem:

\vspace{1ex}

\begin{a2theorem}\label{CRASth2}
\par - (i) If $\lambda_1<0$ and $\delta\leq \delta_1$, then there
exists a positive bounded solution $p_\delta$ of
{\rm{(\ref{eq_sta})}} such that $p_\delta \geq \ds{-\frac{\lambda_1
\phi}{\overline{\nu}(1+\underline{\phi})}} $ (in particular $\max
p_\delta \geq \frac{-\lambda_1}{2\overline{\nu}}$).
\par (ii) If $\lambda_1<0$ and $\delta
> \delta_2$, or if $\lambda_1\geq 0$,  there is no positive bounded
solution of {\rm{(\ref{eq_sta})}}.
\end{a2theorem}

\vspace{1ex}

The proof relies on monotone methods of sub- and super-solutions.
For the existence result (i), we have computed a sub-solution of the
form $\kappa \phi$ with $\kappa > 0$. The optimal value of $\kappa$,
in the sense that it gives the highest value of $\delta_1$, is
$\kappa_0=\ds{-\lambda_1/(\overline{\nu}+\overline{\nu}\underline{\phi})}$.
We have numerically computed the values of $\delta_1$ and $\delta_2$
in several particular examples of sp-case (see Figure \ref{fig}).
The results illustrate the effect of environmental fragmentation on
the maximum sustainable yield, and show that the interval
$(\delta_1,\delta_2]$ on which we have no theoretical information
can be very narrow (see Figure \ref{fig}-(c)).

\begin{figure} \centering
\subfigure[]{
\label{fig+2}
\includegraphics*[width=4.1cm]{boules_k=2.eps}}
\subfigure[]{
\label{fig+10}
\includegraphics*[width=4.1cm]{boules_k=10.eps}}
\subfigure[]{
\label{fig+c}
\includegraphics*[width=6.5cm, height=4.1
cm]{courbes.eps}}
 \caption{$N=2$, $A=I_2$, $\nu\equiv 1$, $h\equiv 1$ and
$\mu(x)$ is $(1,1)$-periodic and takes two values,  $\mu\equiv-1$ on
$\Omega_-$ and $\mu\equiv 10$ on $\Omega^+$, where $\Omega^+$
consists on $k^2$ equally-spaced disks such that, on each period
cell $[0,1]^2$, $|\Omega^+\cap [0,1]^2|=1/2$, and
$\Omega^-=\R^2\backslash \Omega^+$. (a) A period cell with $k=2$ (b)
$k=10$; $\Omega^+$ is represented in black. (c) The values of
$\delta_1$ (continuous line) and $\delta_2$ (dashed line) in
function of $k$.}
 \label{fig}
\end{figure}

 Let us turn to the study of the
evolution equation (\ref{eq_evo2}). We assume that $\lambda_1<0$
 and $\epsilon$ is such that $\ds{\varepsilon_0:=2\frac{\varepsilon \overline{\nu}}{
\underline{\phi}}}<\ds{\frac{-\lambda_1}{2}}$;  we prove the
following theorem:

\vspace{1ex}

\begin{a2theorem} Let $u(t,x)$ be the solution of
{\rm(\ref{eq_evo2})} with initial data $u(0,x)=p(x)$ defined in
Remark \ref{rem1}. Then $u$ is non-increasing in $t$ and we have the
following asymptotic behaviour \par (i) if $\delta\leq \delta_1$,
$u(t,x)\to p_\delta(x)$ uniformly in $\Omega$ as $t\to +\infty$,
where $p_{\delta}$ is the unique positive maximal solution of
{\rm{(\ref{eq_sta})}}; and \par (ii) if $\delta
> \delta_2$, then $u(t,x)<  \varepsilon_0$
for $t$ large enough.
 \label{CRASth3}
\end{a2theorem}

\vspace{1ex}

\noindent In the above theorem, we assume that $u(0,x)=p(x).$ This
means that harvesting starts on a stabilized population governed by
the standard Fisher model without external forcing. \vspace{1ex}
\begin{a2remark}
{\rm These results are sharper than those which could be obtained by
a standard La Salle invariance principle, since we obtain here
discriminatory bounds on $\delta$, which determine the asymptotic
behaviour of the solutions.}
\end{a2remark}
\vspace{1ex}

\section{Time-periodic forcing}\label{sec3}

In this section we consider the general equation (\ref{eq_evo}) in
the {\bf bounded case}, with $\omega > 0$ defined as the frequency
of the forcing term. All the results are proved in \cite{cr}. Let us
introduce $T:=\omega^{-1}$. It is known that under the above
assumptions on $A(x)$, $\mathcal{A}u=-\nabla \cdot(A(x) \nabla u)$
is a sectorial operator with domain $\mathcal{D}(\mathcal{A})=\{u\in
H^2(\Omega), \mbox{ s. t. }
\partial_n u =0\ \mbox{ on } \partial \Omega \}$ (see e.g.
\cite{paz}). As a consequence, $-\mathcal{A}$ generates an analytic
semigroup $e^{-\mathcal{A}t}$ on $L^2(\Omega)$. Let $\{V^{2
r}\}_{\{r\geq 0\}}$ be the family of interpolation spaces generated
by the fractional powers of $\mathcal{A}$, where $V^{2
r}=\mathcal{D}(\mathcal{A}^{r})$ (see \cite{sell} for details). The
existence of a $T$-periodic solution of the equation (\ref{eq_evo})
can be reached by several procedures (e.g. averaging method
\cite{hal}). We present here a result on the existence of a
hyperbolic $T$-periodic solution, which is related to the robustness
of a hyperbolic stationary solution of the autonomous equation
(\ref{eq_evo2}), with $\delta h(x)= \int_{0}^1 f(s, x)ds$. More
precisely, \vspace{1ex}
\begin{a2theorem}\label{bogozthm}
Assume that equation {\rm(\ref{eq_evo2})} has a hyperbolic
stationary solution $q \in V^{2 r}$, $0\leq r \leq 1$. Then there
exists $\omega^{*} > 0$ such that for every $\omega \geq
\omega^{*}$, the problem {\rm(\ref{eq_evo})} possesses a hyperbolic
$T$-periodic solution $u_{\omega}(t)$ such that for any $t\in
[0,T]$, $u_{\omega}(t)$ lives in a $V^{2 r}$-neighborhood of $q$.
Furthermore if $\omega \rightarrow +\infty$, then $u_{\omega}(t)
\rightarrow q$ in $V^{2 r}$.
\end{a2theorem}
\vspace{1ex}

The proof uses similar arguments as the one of \cite{sell} Theorem
76.1, and is therefore based on a Lyapunov-Perron type argument; the
existence of such a hyperbolic periodic orbit is achieved via a
fixed point argument on the following operator:

\begin{equation*} \label{ope} \xi \rightarrow \mathcal{T}(f)\xi
:=\int_{-\infty}^t Q e^{-L(t-s)}(E(q,\xi)+f(ws,\cdot))ds...
\end{equation*}
\begin{equation*}
...-\int_t^{+\infty}P e^{-L(t-s)} (E(q,\xi)+f(ws,\cdot))ds,
\end{equation*}

where $L=\mathcal{A}-(\mu(x)-2\nu(x)q)\mathcal{I}$,
$E(q,\xi)=-2\nu(x)\xi^2$, $\xi$ belongs to a subset of
$L^{\infty}(\R, V^{2r})\cap C^0(\R,V^{2r})$,  and $P$ and $Q$ are
the associated projectors with the exponential dichotomy for
equation (\ref{eq_evo2}) related to the existence of a hyperbolic
stationary solution.

The main interest of Theorem \ref{bogozthm} is that it gives a
simple sufficient condition to ensure the existence of a
$T$-periodic solution of (\ref{eq_evo}) and that it allows to
localize in physical space where this solution can appear. Another
interesting aspect of this theorem is that it reduces the study of
existence and stability of a $T$-periodic solution of (\ref{eq_evo})
to that of the hyperbolic equilibria of the autonomous version
(\ref{eq_evo2}). For instance we get as an application of Theorems 2
and 4 for $\lambda_1 < 0$ and $f(wt,x)=\delta g(wt,x)$ with $\alpha<
\int_0^1 g(s,x)ds<\beta$ for all $x\in \Omega$, that if $\delta\leq
\delta_1$ and $\omega$ sufficiently large, then there exists a
stable non-trivial $T$-periodic solution $u_{\omega,\delta}$ of
$(\ref{eq_evo})$ in a neighborhood of a solution $p_{\delta}$ of
(\ref{eq_sta}).

\vspace{3ex}

{\bf Note added for this version on ArXiV:} The reference \cite{rc}
cited here, corresponds the article of the authors entitled ``On
Population Resilience to External Perturbations" which has been
published in {\it SIAM J. Appl. math (SIAP)}, {\bf 68} (1), (2007)
133-153. We kept here the old reference \cite{rc} as in the
original article published in {\it C. R. Acad. Sci. Paris}, Ser. I,
343: 307-310; before the SIAP article. The reference \cite{cr} below
is still under preparation.

config: arxiv


TITLE: Calculus Circle Related rates circle proof
QUESTION [0 upvotes]: NOTE: THIS QUESTION HAS ALREADY BEEN ANSWERED AND CAN BE FOUND AT THIS LINK (Related rates circle problem)
Question:
Two circles $A$ and $B$ have the same center. The radius of the inner circle $A$ is increasing at a rate of $1$ unit/sec, and the radius of the larger circle $B$ is also increasing such that the area between the two circles is always $10\pi$. When the radius of $A$ is 5, how fast is the radius of $B$ increasing?
So I know that this question has been answered already in the past, but I'm wondering if there is another solution. Could this problem perhaps be solved with differentiation? All I'm asking is if there is another way to solve the problem (another solution perhaps). My thinking was rather than substitute variables for others like the previous solution did (smaller radius is R and 2R and so forth), we could solve it directly. Of course, this may not be possible, and I'm asking the most brilliant minds in STEM to help me out :D If a solution does arrive, I'd love to see it! Alternate explanations are always possible in math. Note: Could it stick within the realm of Calculus only? Number theory and other advanced topics like that aren't necessary.

REPLY [0 votes]: It can be solved without differentiation although the logic of solving it is based on calculus.
When $r = 5$ and the area between R and r is $10\pi$, then $R = \sqrt35$
For an infinitesimally small change in radius dr, the area of the smaller circle increases by $2\pi r dr$. To maintain the same area of $10\pi$, the larger circle must increase in area by the same amount.
Hence $2\pi r\ dr = 2\pi R\ dR$
$10\pi\ dr = 2\sqrt{35}\pi\ dR$
$5\ dr = \sqrt{35}\ dR$
$dR = \frac{5}{\sqrt{35}}dr$
Therefore $$\frac{dR}{dt} = \frac{5}{\sqrt{35}} \frac{dr}{dt}$$
and $$\frac{dR}{dt} = \frac{5}{\sqrt{35}}\cdot 1$$
$$=\frac{\sqrt{35}}{7} \text{unit/sec}$$


TITLE: Finding a low-degree polynomial vanishing on half the zeroes of a polynomial system
QUESTION [7 upvotes]: Let $f(x)$ be a real polynomial of degree $2d$ without real roots. Let the complex roots be $z_1$, $\bar{z_1}$, $z_2$, $\bar{z_2}$, ..., $z_d$, $\bar{z_d}$ with $z_i$ in the upper half plane. Let $g(x) = \prod(x-z_i)$, a complex polynomial of degree $d$. Is there a way to compute the coefficients of $g$ which is better than finding the roots of $f$?
That was a simpler version of what I actually want. My actual problem is in two variables: Let $f_1(x,y)$ and $f_2(x,y)$ be real polynomials of degree $m$ and $n$, with all the roots of $f_1=f_2=0$ isolated and nonreal. Let $p_1$, $\bar{p}_1$, ..., $p_{mn/2}$, $\bar{p}_{mn/2}$ be the roots of $f_1=f_2=0$, with the $y$-coordinates of the $p_i$ in the upper half plane. I want to compute a basis for the vector space of degree $d$ complex polynomials in $(x,y)$ which vanish on the $p_i$. Again, is there a method which is better than finding the $p_i$?
In both cases, it is an easy Galois theory exercise to show that there is no solution is radicals, so the question is about numerical methods.

REPLY [1 votes]: As @Federico notes (but does not say explicitly), the magic words are "spectral factorization" -- for an algorithm see here. I should say that it is very far from clear to what extent the fancy algorithms are better than just factoring the polynomial, it probably depends on many things.


TITLE: is the intersection with a Lattice still a Lattice?
QUESTION [0 upvotes]: Given a lattice A in $R^n$, and a subspace B of $R^n$. is the intersection $A \cap B$ a lattice?
Thanks

REPLY [1 votes]: Well, is $A\cap B$ a discrete set of points in a Euclidean space? Yes. Is it closed under addition and taking opposite vectors? Also yes. Thus, it is a lattice. It may not have full rank in $B$ though; in particular, it may have rank $0$ (i. e. consist only of the origin).


TITLE: Why is it possible to ignore gamma factor in uniformly accelerated motion in SR?
QUESTION [0 upvotes]: I have a doubt on one step of the derivation of the hyperbolic relations between $t$ and $\tau$ and $x$ and $\tau$ for uniformly accelerated frames in one dimension.
They come from $2$ differential equations:
$$
\begin{align}
\frac{\mathrm{d}U^0}{\mathrm{d}\tau}&=aU^1 \\
\frac{\mathrm{d}U^1}{\mathrm{d}\tau}&=aU^0
\end{align}
$$
That are valid if a$^2$ = a$^2$. ('a' being the 4-vector for acceleration, and 'a' the local acceleration observed for any object in the accelerated frame)
But that statement is true only when $v = 0$, that is, when the inertial frame has momentarily the same speed of the accelerated one.
Of course, there will always be a comoving inertial frame for which a$^2$ = a$^2$.
And it is true that any inertial frame is as good as any other to do the maths in SR. But if one is choosed, as I understand, it must be kept all the way.
In that case how can I ignore the term $\gamma^6$, (containing $v$ as a variable), in the equation: a$^2$ = $\gamma^6$a$^2$?

REPLY [1 votes]: if one is choosed, as I understand, it must be kept all the way.

Not in this case. The concept of proper acceleration involves an instantaneously comoving inertial frame in which the instantaneous acceleration is measured. Without a continuous sequence of different inertial frames, each comoving with the accelerating object at faster and faster speeds, constant proper acceleration has no meaning.


TITLE: Question about Lang's proof of Jordan-Holder theorem
QUESTION [2 upvotes]: This is on page 22 of Lang's Algebra book.  Here is the statement and proof of the theorem:
Let $G$ be a group, and let $G= G_1\supset G_2\supset\cdots\supset G_r = \{e\}$ be a normal tower such that $G_{i}/G_{i+1}$ is simple and $G_i \neq G_{i+1}$ for $i = 1,\ldots,r-1$.  Then any other normal tower of $G$ havingthe same properties is equivalent to this one.
Proof: Let $G= H_1\supset H_2\supset\cdots\supset H_s = \{e\}$ be another such normal tower with all quotients being simple groups. Define $G_{ij} = G_{i+1}(H_{j}\cap G_{i})$.  We observe that for each $i$, there exists preciesly one index $j$ such that $G_i/G_{i+1} = G_{ij}/G_{i,j+1}$.  Thus the sequence of non-tribial factors for the original tower, or the refined tower, is the same.
So I'm not quite following this proof.  Why is it true that there is only one index $j$ s.t. "$G_i/G_{i+1} = G_{ij}/G_{i,j+1}$"? and is Lang using that fact to somehow show that the two towers are identical? or is he showing that the $G_{ij}$ refinement is identical to the original tower?  I had some other observation which I think is important and that is if $G_i/G_{i+1}$ is simple then a refinement of the normal tower cannot contain a group between $G_i$ and $G_{i+1}$.  So it seems what Lang is showing is that if there is another normal tower, then you can refine your original normal tower.  I'd really be interested in figuring out this proof because the other proofs I found on it used induction and this one seems pretty slick.

REPLY [2 votes]: You analyzed it correctly. By Schreier's Theorem any two normal towers with simple factors have a equivalent refinement. But since factors are simple their refinements are trivial. Hence all normal towers with simple factors are equivalent.


TITLE: Difficult inverse tangent identity
QUESTION [3 upvotes]: Prove that:
$$\arctan\left(\frac{\sqrt{1 + x} - \sqrt{1-x}}{\sqrt{1 + x} + \sqrt{1-x}} \right) = \frac{\pi}{4} - \frac{1}{2}\arccos(x), -\frac{1}{\sqrt{2}} \le x \le 1$$

I'd multiply the inside of $\arctan$ by the conjugate of the denominator.
I get:
$$\arctan\left(\frac{1 - 1\sqrt{1 - x^2}}{x} \right)$$
But that is still very difficult.
Any HINTS, no solutions?

REPLY [2 votes]: In the other way round, let
$$\arctan\left(\frac{\sqrt{1 + x} - \sqrt{1-x}}{\sqrt{1 + x} + \sqrt{1-x}} \right) =y$$
$\implies -\dfrac\pi2\le y\le\dfrac\pi2\  \ \ \ (1)$ and $\tan y=\dfrac{\sqrt{1 + x} - \sqrt{1-x}}{\sqrt{1 + x} + \sqrt{1-x}}$
Applying Componendo and dividendo,  $$\dfrac{\sqrt{1 + x}}{\sqrt{1 - x}}=\dfrac{1+\tan y}{1-\tan y}$$
Squaring we get,  $$\dfrac{1+x}{1-x}=\dfrac{1+\tan^2y+2\tan y}{1+\tan^2y-2\tan y}$$
Again applying Componendo and dividendo, $$x=\dfrac{2\tan y}{1+\tan^2y}=\sin2y$$
Now $-\dfrac1{\sqrt2}\le x\le1\implies-\dfrac\pi4\le2y\le\dfrac\pi2\  \ \ \ (2)$ (using $(1)$)
Finally, $2y=\arcsin x$ if $-\dfrac\pi2\le2y\le\dfrac\pi2$ which is satisfied by $(2)$
$\implies2y=\arcsin x=\dfrac\pi2-\arccos x$


TITLE: Fourier transform of a signal
QUESTION [0 upvotes]: I have the following signal and need to derive it's Fourier transform:

I just started learning Fourier transform and don't know how to solve this kind of question. I know though how to derive the Fourier transform for: $$cos(2\pi f_0t)$$
$$\mathcal{F}\{cos(2\pi ft)\}=\int_{-\infty}^{\infty}cos2\pi f_0*e^{-j2\pi ft}dt $$
$$
=\int_{-\infty}^{\infty}\frac{1}{2}(e^{-j2\pi(f-f_0)t}dt
+\int_{-\infty}^{\infty}\frac{1}{2}(e^{-j2\pi(f+f_0)t}dt$$
$$
=\frac{1}{2}(\delta(f-f_0)+\delta(f+f_0))
$$

REPLY [1 votes]: We can write the function as
$$
g(t)=\underbrace{A\cos(2\pi f_c t)}_{x(t)}\times\underbrace{\mathrm{rect}(t/T)}_{y(t)}
$$
where $T=\frac{2}{f_c}$ and the rectangular function is defined as
$$
\mathrm{rect}(t) =\begin{cases} 0 & \mbox{if } |t| > \frac{1}{2} \\ 1 & \mbox{if } |t| < \frac{1}{2}. \\ \end{cases}
$$
The fourier transform of a product of signals is the convolution of the Fourier transforms of the signals $$
\mathcal{F}\left\{g(t)\right\}=G(f)=X(f)*Y(f)
$$ with
$$\begin{align}
\mathcal{F}\left\{ A\cos(2\pi f_c t) \right\}&=X(f)=\frac12\left[\delta(f-f_c)+\delta(f+f_c)\right]\\
\mathcal{F}\left\{\mathrm{rect}(t/T) \right\}&=Y(f)=T\frac{\sin(\pi Tf)}{\pi T f}=\frac{\sin(2\pi f/f_c)}{\pi f}
\end{align}
$$
Observing that $z(t)*\delta(t-T)=z(t-T)$ we have
$$
\begin{align}
G(f)&=\frac12\left[Y(f-f_c)+Y(f+f_c)\right]\\
&=\frac12 \left[\frac{\sin(2\pi (f-f_c)/f_c)}{\pi (f-f_c)}+\frac{\sin(2\pi (f+f_c)/f_c)}{\pi (f+f_c)}\right]\\
&=\frac{f}{\pi}\frac{\sin\left(2\pi {f}/{f_c}\right)}{f^2-f_c^2}
\end{align}
$$


TITLE: Shell method error
QUESTION [2 upvotes]: I was attempting to solve this problem using the shell method:

The region R in the first quadrant is enclosed by the lines $x=0$ and
  $y=5$ and the graph of $y=x^2+1$. The volume of the solid generated when R
  is revolved around the y axis is

The correct answer is $8\pi$.
I attempted to solve this using the shell method as follows:
$\int_0^2 (2\pi*x*(x^2+1)) dx$. However, I get $12\pi$ as a result.
Solving with the disk method, I get the correct answer:
$\int_1^5 (\pi*(y-1))dy = 8\pi.$
What mistake did I make using the shell method?

REPLY [2 votes]: For the shell method we should assume
$$\int_0^2 2\pi R H dx\int_0^2 [2\pi \cdot x \cdot (5-(x^2+1))] dx=2\pi\int_0^2 (4x-x^3) dx=2\pi\left[2x^2-\frac{x^4}4\right]_0^2=8\pi$$


TITLE: Let $G$ be a group, $G'=[G,G]$ and $G''=[G',G']$ the first and second derived subgroups and assume $G''$ is cyclic. Prove that $G''\subset Z(G')$.
QUESTION [7 upvotes]: I'm trying to prove the following, but I'm stuck and I don't see how to continue. Any help is much appreciated!

Let $G$ be a group, $G'=[G,G]$ and $G''=[G',G']$ the first and second derived subgroups and assume $G''$ is cyclic. Prove that $G''\subset Z(G')$.

My work this far: Since $G''$ is cyclic, it is abelian. Since it is the commutator subgroup of $G'$, it is also known that $G''$ is normal. Thus (using a theorem from my syllabus), there exists a homomorphism $g:G'/G''\to\mathrm{Aut}(G'')$ such that $g(aG'')=\phi_{a|G''}$ for $a\in G'$, where $\phi_{a|G'}:G''\to G'':x\mapsto axa^{-1}$, thus the conjugation map by $a$. Now it suffices to proof $\phi_{a|G'}=Id_{G'}$ for all $a\in G'$.
But how to prove this? I don't see it. The work I did this far follows a hint that was given for the question.

REPLY [3 votes]: In general, if $H$ is a subgroup of $G$, then $N_G(H)/C_G(H) \hookrightarrow Aut(H)$, by conjugation. Now take $H=G''$, being cyclic. Then $Aut(G'')$ is abelian. Since $G''$ is normal in $G$ we have $N_G(G'')=G$ and so $G/C_G(G'')$ is abelian, whence $G' \subseteq C_G(G'')$. That is, $G'$ centralizes $G''$, or equivalenty $G'' \subseteq Z(G')$.