Is there a graph that matches the conjectured maximum path partition number for $\Delta=\delta+1$? Let $G$ be a graph with $n$ vertices where $\delta$ is the minimum vertex degree and $\Delta$ is the maximum vertex degree. Then the path partition number of $G$, $\mu(G)$, is the minimum number of paths needed to partition the vertices of $G$ into paths. $K_n$ is the complete graph on $n$ vertices and $K_{n,m}$ is the complete bipartite graph with one part having $n$ vertices and the other having $m$ vertices.
In arXiv:2212.12793 On the path partition of graphs, M.Kouider, M.Zamime, they mention the following conjecture of Magnant, Wang and Yuan:
$ µ(G) ≤ \max\{\frac{n}{\delta+1},\frac{(\Delta-\delta)n}{(\Delta+\delta)}\}$
Note that that $\Delta\geq\delta$ by definition and $$\frac{n}{\delta+1}\leq\frac{(\Delta-\delta)n}{(\Delta+\delta)}$$ if $\Delta\geq\delta+2$ and $$\frac{n}{\delta+1}>\frac{(\Delta-\delta)n}{(\Delta+\delta)}$$ if $\Delta<\delta+2$.
In the paper it is noted that if this conjecture is true then it is tight as if $\Delta\geq\delta+2$ then the collection of $\frac{n}{\Delta+\delta}$ disjoint copies of $K_{\delta,\Delta}$ requires $\frac{(\Delta-\delta)n}{(\Delta+\delta)}$ paths to partition its vertices as each disjoint $K_{\delta,\Delta}$ would need at least $\Delta-\delta$ paths. This graph clearly has minimum and maximum vertex degree of $\delta$ and $\Delta$ respectively and has $n$ vertices so matches the maximum conjectured $\mu(G)$.
If $\Delta=\delta$ then the collection of $\frac{n}{\delta+1}$ disjoint copies of $K_{\delta+1}$ requires $\frac{n}{\delta+1}$ paths to partition its vertices. This graph clearly has equal minimum and maximum vertex degree of $\delta=\Delta$ and has $n$ vertices so matches the maximum conjectured $\mu(G)$.
My question is: Is there is a graph with $n$ vertices and $\Delta=\delta+1$ that matches the maximum conjectured $\mu(G)$ i.e. a graph $G$ such that $\mu(G)=\frac{n}{\delta+1}=\frac{n}{\Delta}$?
The closest I can come is to find such a graph with $\mu(G)=\frac{n}{\delta+1}-1$. To find this, start with a collection of $\frac{n}{\delta+1}$ disjoint copies of $K_{\delta+1}$. This has $n$ vertices. Then take $2$ of those copies of $K_{\delta+1}$, choose one vertex from each of them and add an edge between them. Then those chosen vertices have vertex degree $\delta+1$ and the other vertices have vertex degree $\delta$ so clearly the minimum vertex degree is $\delta$ and the maximum vertex degree is $\delta+1$. $\frac{n}{\delta+1}-1$ paths are required to partition the vertices as there are $\frac{n}{\delta+1}-2$ disjoint copies of $K_{\delta+1}$ and there are also the two connected $K_{\delta+1}$ graphs.
 A: When $\Delta(G)=\delta(G)+1$, we can find arbitrarily large $n$-vertex graphs $G$ with $\mu(G) = \frac{n-1}{\delta(G)+1}$, which is almost what we want. When $n = k(\delta+1)+1$ for $k\ge 2$, take $k-1$ copies of $K_{\delta+1}$ and one copy of $\delta+2$, to get a graph with $\mu(G)=k$, $\delta(G)=\delta$, and $\Delta(G)=\delta+1$.
At least when $\delta(G)\le2$, we cannot do better.
When $\delta(G)=1$ and $\Delta(G)=2$, every component of $G$ is a path, so we can only have $\mu(G) = \frac n2$ if there are $\frac n2$ components. But then, each component needs to be a $2$-vertex path, and we end up with $\Delta(G)=1$ after all.
When $\delta(G)=2$ and $\Delta(G)=3$, we can take the paper Path partitions of almost regular graphs by Magnant, Wang, and Yuan as a starting point. This is the original source of the conjecture, and they prove the $\delta=1$ and $\delta=2$ cases.
We have to look more closely at their proof to get what we want. When $G$ has no two adjacent vertices of degree $2$, Magnant et al. prove the upper bound of $\frac{\Delta(G)-\delta(G)}{\Delta(G)+\delta(G)} \cdot n$ directly, which in our case gives us $\frac {n}{5}$; better than $\frac {n}{3}$. Otherwise, we consider several cases:

*

*If two adjacent vertices $u,v$ of degree $2$ have no common neighbor, contract them to a single vertex and apply the bound to the resulting to get $\frac{n-1}{3}$.

*If their common neighbor $x$ has degree $2$, we have a $K_3$ component, which we'll deal with at the end.

*If $x$ has degree $3$, find a maximal path $u,v,x,y_1, \dots, y_t$ where $y_1, \dots, y_t$ have degree $2$ and $y_t$'s other neighbor has degree $3$. If $t\ge 1$, then we can delete that path (of length $4$) and cover the remaining graph by at most $\frac{n-4}{3}$ paths by induction, for a total of $\le \frac{n-1}{3}$.

*If $x$ has degree $3$ and its third neighbor $y$ has degree $3$, let $z_1, z_2$ be $y$'s other neighbors. To induct, we can try to delete delete $u,v,x,y$ and possibly add an edge $z_1 z_2$ to preserve minimum degree. This works unless one of $z_1, z_2$ has degree $2$ and there is already an edge $z_1 z_2$.

*In that final case, suppose $z_1$ has degree $2$. Take the path $u,v,x,y,z_1,z_2$. As in step 3, extend that path to vertices of degree $2$ (if there are any) until it reaches a vertex of degree $3$. Delete that path and induct.

This is a fair bit of casework (it is based on Magnant et al.'s proof but a tiny bit more complicated) but in the end it shows that we can always improve a tiny bit on $\frac n3$ unless the two adjacent degree-$2$ vertices we found are part of a $K_3$ component. But if the entire graph is $K_3$ components, then it does not have maximum degree $3$ - and if not, then there will be a component where we can improve on the $\frac n3$ bound to get $\mu(G) \le \frac{n-1}{3}$ or better.

When $\delta(G) \ge 3$, I suspect that there is also no extremal construction with $\Delta(G) = \delta(G)+1$, but if so, it's going to be tough to prove when the original conjecture is still open.
