Long paths and cycles in subgraphs of the cube
Let $Q_n$ denote the graph of the $n$-dimensional cube with vertex set $\{0,1\}^n$ in which two vertices are adjacent if they differ in exactly one coordinate. Suppose $G$ is a subgraph of $Q_n$ with average degree at least $d$. How long a path can we guarantee to find in $G$?Our aim in this paper is to show that $G$ must contain an exponentially long path. In fact, we show that if $G$ has minimum degree at least $d$ then $G$ must contain a path of length $2^d-1$. Note that this bound is tight, as shown by a $d$-dimensional subcube of $Q_n$. We also obtain the slightly stronger result that $G$ must contain a cycle of length at least $2^d$ and prove analogous results for other `product-type' graphs.
\section{Introduction} 


Given a graph $G$ of average degree at least $d$, a classical result of Dirac \cite{dirac} guarantees a path of length $d$ in $G$. Moreover, this bound is best possible as can be seen from $K_{d+1}$.

Inside the cube $Q_n$ can we improve this bound? That is, given a subgraph $G$ of $Q_n$ with average degree at least $d$, what is the length of the longest path in $G$? The edge isoperimetric inequality for the cube (\cite{bernstein}, \cite{harper}, \cite{hart}, \cite{lindsey}, see \cite{com} for background) says that any subgraph of average degree at least $d$ must have size at least $2^d$. In light of this, the above linear bound seems very weak. A natural subgraph of $Q_n$ with average degree at least $d$ is the $d$-dimensional cube $Q_d$, the analogue of the complete graph in $Q_n$, which contains a path of length $2^d-1$. Must the size of the longest path in $G$ also be exponential?

The main result of this paper answers this question in the affirmative.

\begin{thm}
{
\label{mainthm}
Every subgraph $G$ of $Q_n$ with minimum degree $d$ contains a path of length $2^{d}-1$.
}
\end{thm}

Note that this is best possible as shown by a $d$-dimensional subcube of $Q_n$. In fact, the proof of Theorem \ref{mainthm} shows that we can always find a longer path in $G$ unless it is isomorphic to $Q_d$. Using the well known fact that every graph with average degree at least $d$ contains a subgraph with minimum degree at least $\frac{d}{2}$ we obtain the following corollary to Theorem \ref{mainthm}.

\begin{cor}
{
\label{corollary} Every subgraph $G$ of $Q_n$ with average degree at least $d$ contains a path of length at least $2^{\frac{d}{2}}-1$.
}
\end{cor}

We do not know a tight bound for average degree $d$. We also obtain the corresponding result for the length of the longest cycle in subgraphs of $Q_n$ with large minimum degree.

\begin{thm}
{
\label{cyclethm}
Every subgraph $G$ of $Q_n$ with minimum degree $d$ contains a cycle of length at least $2^d$.
}
\end{thm}

In Section 2 we give an overview of the proofs of Theorems \ref{mainthm} and \ref{cyclethm}. The theorems themselves are then proved in Sections 3-7.

In Section 8 we show that the lower bound from Theorems \ref{mainthm} and \ref{cyclethm} also extends to subgraphs of the grid graph $\Z^n$ and the discrete torus $C_k^n$, for all $k\geq 4$. We also give a generalization of Theorem \ref{mainthm} and \ref{cyclethm} to general `product-type' graphs and  make some conjectures.



























\section{Overview}

As in the statement of Theorem \ref{mainthm}, let $G$ be a subgraph of $Q_n$ with $\delta (G)\geq d$. We will view the vertices of $Q_n$ as elements of the power set of $[n]$, $\mathcal{P}[n]$. 

A plausible approach to proving Theorem \ref{mainthm} is to split $G$ along some direction $i$ to obtain two induced subgraphs $G_1$ and $G_2$ consisting of those vertices of $G$ respectively containing and not containing $i$, for some $i\in [n]$. Provided such a direction is chosen to ensure that $G_1, G_2\neq \emptyset $, we have $\delta (G_i)\geq d-1$ and by induction on Theorem \ref{mainthm} we have a path of length $2^{d-1}-1$ in each subgraph. If we could join these two paths into one we would clearly be done. However, as Theorem \ref{mainthm} provides no information on where these paths start or end, we can not expect to be able to do this. 

This suggests that we strengthen Theorem \ref{mainthm} to guarantee an exponentially long path between \emph{any} two vertices $x$ and $y$ of $G$. In general this is not possible -- for example, consider the graph $G'$ obtained by removing all but one edge $xy$ of direction $d+1$ from the ($d+1$)-dimensional cube $Q_{d+1}$. 

However this graph is not 2-connected. The following theorem says that this is the only obstruction to such a strengthening.

\begin{thm}
{
\label{conn}
Let $G$ be a 2-connected subgraph of $Q_n$ and $a$ and $b$ be distinct vertices of $G$. Suppose that $d_G(z) \geq d$ for all $z \in G-\lbrace a,b\rbrace$. Then $a$ and $b$ are joined by a path of length at least $2^{d}-2$. Furthermore, unless $G$ is isomorphic to $Q_d$ with $a$ and $b$ at even Hamming distance, $G$ contains an $a-b$ path of length at least $2^{d}-1$.
}
\end{thm}

Note that we do not assume that $a$ or $b$ have degree at least $d$ in Theorem \ref{conn}. This slight weakening of the minimum degree condition will allow us to use induction on various subgraphs of $G$ which would otherwise not be available. 

Before continuing with the overview we make a small diversion to introduce some definitions: these are standard (e.g. see \cite{mgt}).
\\



A subgraph $B$ of a graph $G$ is a \emph{block} of $G$ if $B$ is either a bridge of $G$ or forms a maximal 2-connected subgraph of $G$. By maximality, $|B_1\cap B_2|\leq 1$ for any two blocks $B_1$ and $B_2$ of $G$ and $G-E(B)$ contains no $x-y$ path between distinct vertices $x,y$ in a block $B$. Therefore if any two blocks intersect, their common vertex must be a cutvertex and conversely every cutvertex lies in at least two blocks. Since every cycle is 2-connected and an edge is a bridge iff it does not lie in any cycle, every graph $G$ decomposes uniquely into its blocks $B_1,\ldots, B_p$ in the sense that:
\begin{equation*}
{
E(G)=\bigcup_{i=1}^p E(B_i) \mbox{ and } E(B_i)\cap E(B_j)=\emptyset \mbox{ if } i\neq j.
}
\end{equation*}

Suppose now that $G$ is connected. Let $\mathcal{B}(G)$, the \emph{block-cutvertex graph} of $G$, be the bipartite graph with bipartition $(\mathcal{B},\mathcal{C})$ where $\mathcal{B}$ is the set of blocks of $G$, $\mathcal{C}$ is the set of cutvertices of $G$ with $Bc$ an edge if $c\in B$. For a connected graph $G$, $\mathcal{B}(G)$ is a tree. 

The leaves of this tree are all elements of $\mathcal{B}$ and are called \emph{endblocks}. Given an endblock $E$ we will denote its unique cutvertex by cutv$(E)$. Note that a graph $G$ has only one endblock iff it is 2-connected.
\vspace{.2cm}






We now return to the overview of the proof of Theorem \ref{conn}.

\begin{lem}
 {
\label{splitting}
Let $G$ be a connected subgraph of $Q_n$ with $a$ and $b$ distinct vertices of $G$. Then there exists a partition of $G$ into two connected subgraphs $G_a$ and $G_b$ such that $a\in G_a$, $b\in G_b$ and for all $v\in G_c$, $d_{G_c}(v)\geq d_G(v)-1$, where $c\in \{a,b\}$.
} 
\end{lem}

\begin{proof}
 {
Picking a splitting direction $i$ such that $a$ and $b$ differ in coordinate $i$ and forming $G_1$ and $G_2$ as before, we have $a\in G_1$ and $b\in G_2$. Let $C_b$ be the connected component of $G_2$ containing $b$. Taking $G_a$ to be the connected component of $G-C_b$ containing $a$ and $G_b=G-G_a$ we are done.
 }
\end{proof}






A central observation in the proof of Theorem \ref{conn} is that, provided $d\geq 3$, given any endblock $E$ of $G_a$ with $a\notin E$, by induction on Theorem \ref{conn}, $E$ contains a path of length at least $2^{d-1}-2$ from $\mbox{cutv}(E)$ to any $y\in E-\mbox{cutv}(E)$ -- here $d\geq 3$ guarantees the $E$ is 2-connected and not a bridge. Since $G$ is 2-connected there must exist $y\in E-\mbox{cutv}(E)$ with a neighbour in $G_b$. Thus endblocks like $E$ guarantee `endblock paths' of length at least $2^{d-1}-1$ from a point in $G_a$ to one in $G_b$. If we can find a path from $a$ to $b$ containing at least two such endblock paths we would almost be done (we might still be short two or three vertices to give the $2^{d}-2$ or $2^d-1$ bound in $G$).

For ease of exposition we will prove the following weakening of Theorem \ref{conn} first. It will allow the reader to focus on the main ideas of the proof of Theorem \ref{conn} without some distracting details needed to ensure that an $a-b$ path formed from endblock paths is not slightly too short.

\begin{thm}
{
\label{connmod}
Let $G$ be a 2-connected subgraph of $Q_n$ and $a,b\in V(G)$. Suppose that $d_G(z) \geq d$ for all $z \in V(G)-\lbrace a,b\rbrace$. Then $G$ contains an $a-b$ path of length at least $2^{d-1}$. 
}
\end{thm}

Another slight technicality that creeps into the proof of Theorem  \ref{conn} and \ref{connmod} is the possibility that the only partitions of $G$ into $G_a$ and $G_b$ as in Lemma \ref{splitting} above, have $a$ with just one neighbour in $G_a$ or $b$ with just one neighbour in $G_b$. While all cases can be dealt with simultaneously, we felt for clarity's sake it is easier to first restrict attention to the case where a partition direction $i$ exists for which both $d_{G_a}(a)\geq 2$ and $d_{G_b}(b)\geq 2$. 
\\

Theorem \ref{connmod} is proved in Sections 3-6. Sections 3-5 will focus on the above case, that is, where we can find a partition direction $i$, such that $d_{G_a}(a)\geq 2$ and $d_{G_b}(b)\geq 2$. Section 3 will describe the block-cutvertex decomposition structure of $G_a$ and $G_b$ on the absence of an $a-b$ path of length $2^{d-1}$ formed by joining at least two endblock paths together and Section 4 describes how the endblocks of $G_a$ interact with those of $G_b$. In Section 5 we show that if $G$ does not contain a path from $a$ to $b$ containing at least two endblock paths then the conditions of Theorem \ref{connmod} hold for a smaller subgraph of $G$. This allows for an inductive step and completes the proof of Theorem \ref{connmod} in this case.

Section 6 will allow us, using a small modification of the argument from Sections 3-5, to extend from the case $d_{G_a}(a)\geq 2$ and $d_{G_b}(b)\geq 2$ to the general case, therefore proving Theorem \ref{connmod}. 

Finally in Section 7 we show how to adjust the approach in Sections 3-6 to obtain the optimal bound of Theorem \ref{conn}. 

To close this section we note that Theorem \ref{conn} implies Theorem \ref{cyclethm}.
\vspace{0.2cm}

\noindent \textit{Proof of Theorem \ref{cyclethm}:} Take an endblock $E$ in the block cutvertex decomposition of $G$. Clearly $E$ is 2-connected and all vertices in $E-\mbox{cutv}(E)$ have at least $d$ neighbours in $E$. Pick a neighbour $v$ of $\mbox{cutv}(E)$ in $E$. Then by Theorem \ref{conn} $G$ contains a $\mbox{cutv}(E)-v$ path $P$ of length at least $2^d-1$. Combining $P$ with the edge $\mbox{cutv}(E)v$ we obtain the desired cycle. \hspace{5cm} $\square$


























\section{Endblocks in $G_a$ and $G_b$}

To begin we introduce some useful definitions.

\begin{dfn}
{
\emph{
Let $E$ be an endblock in the block-cutvertex decomposition of $G_a$ ($G_b$). The \emph{interior} of $E$ is the set $\mbox{int}(E)=E-\mbox{cutv}(E)$. A vertex $x\in \mbox{int}(E)$ is said to be an \emph{exit vertex} of $E$ if $x$ has a neighbour in $G_b$ ($G_a$). If this neighbour exists, it is unique and is denoted by $p(x)$, $x$'s \emph{partner}.}
}
\end{dfn}

\begin{dfn}
{
\label{why}
\emph
{
Body$(a)$ is the intersection of all blocks of $G_a$ containing $a$. Let $\mbox {Core}(a)$ consist of those vertices in $\mbox {Body}(a)$ that are not cutvertices of $G_a$.
}
}
\end{dfn}

\begin{dfn}
{
\emph
{
A subgraph $K$ of $G_a$ is said to be a \emph{limb} of $a$ if:}
\begin{itemize}
\item \emph{$a$ is a cutvertex of $G_a$ and $K=G\lbrack C\cup \lbrace a\rbrace \rbrack $ where $C$ is a connected component of $G_a-a $;}

\item \emph{$a$ is not a cutvertex of $G_a$ and $K=G\lbrack C \rbrack $ where $C$ is a connected component of $G_a-\mbox {Core}(a)$.}
\end{itemize}
\emph{
The \emph{joint} of a limb $K$, Joint$(K)$, is the unique vertex $v\in K\cap \mbox {Body}(E)$.
}
}
\end{dfn}

The reader may find it helpful to examine Figure \ref{intro}. The circles and ellipses will always 
denote blocks in the block-cutvertex decomposition of graph.
\vspace{0.3cm}

\noindent \emph{Proof of Theorem \ref{connmod}.} The proof is by induction on $d$ where the base case $d=2$ is trivial. The proof will last until the end of Section 6. Suppose for contradiction, the theorem fails for $d$ and take $G$ to be a minimal counterexample so that Theorem \ref{connmod} holds for all smaller degrees and all graphs $G'$ with $|G'|<|G|$. The following theorem restricts the possibilities for $G$.
\vspace{0.3cm}



\noindent \textbf{Theorem 2.3$'$.} \emph{Suppose $G$ is a counterexample to Theorem \ref{connmod} so that Theorem \ref{connmod} holds for all smaller degrees and all graphs $G'$ with $|G'|<|G|$. Then there does not exist a direction $i$ such that forming $G_a$ and $G_b$ as in Lemma \ref{splitting}, $d_{G_a}(a)\geq 2$ and $d_{G_b}(b)\geq 2$.}
\vspace{0.2cm}

\noindent \emph{Proof of Theorem 2.3$'$.} The proof will last until the end of Section 5. Suppose for contradiction that such a $G$ and $i$ exist and form $G_a$ and $G_b$ as above from direction $i$. Our first lemma describes the block structure of $G_a$ provided we cannot use endblock paths to form an $a-b$ path of length at least $2^{d-1}$.

\begin{figure}
\centering
\input{intro.pstex_t}
\caption{The diagram displays various parts of $G_a$ and $G_b$. The broken line separates $G_a$ and $G_b$. In $G_a$, $\mbox{Body}(a)\neq \{a\}$ and $a$ has three limbs. In $G_b$, $b$ is a cutvertex and one of its limbs $L$ contains an endblock $F$ with exit vertex $x$.\label{intro}}
\end{figure}



\begin{lem}
{
\label{list}
Given $G$ the following hold:
\begin{itemize}
{
\item[\emph{(i)}] Every endblock of $G_a$ which does not contain $a$ in its interior must contain at least two exit vertices.

\item[\emph{(ii)}] $G_a$ is not 2-connected.

\item[\emph{(iii)}] $a$ does not lie in the interior of an endblock in $G_a$.

\item[\emph{(iv)}] $a$ must have at least two limbs.
}
\end{itemize}
}
\end{lem}

\begin{proof}
{

(i)
Suppose not and let $E$ be such an endblock. By the 2-connectivity of $G$, $E$ must contain an exit vertex $x$. If $x$ were its only exit vertex then every $v\in E-\lbrace {\mbox{cutv}(E),x}\rbrace $ has degree least $d$ in $G[E]$ -- such $v$ must exist since $d\geq 3$. 
Then by choice of $G$, $G[E]$ contains a path $P_2$ of length at least $2^{d-1}$ from $\mbox{cutv}(E)$ to $x$. Joining $a$ to $\mbox{cutv}(E)$ in $G_a$ by a path $P_1$ and $p(x)$ to $b$ in $G_b$ by a path $P_3$ we have created a path $P_1P_2P_3$ of length $2^{d-1}$ from $a$ to $b$, a contradiction.

(ii)
Suppose $G_a$ is 2-connected. First consider the case where $G_b$ is not 2-connected. Let $E$ be an endblock in $G_b$ not containing $b$ in its interior and take $x$ to be an exit vertex of $E$ with $p(x)\neq a$ -- this exists by (i). Then by induction on $d$, there are paths $P_1$ in $G_a$ from $a$ to $p(x)$ and $P_2$ in $G[E]$ from $x$ to $\mbox{cutv}(E)$ both of length at least $2^{d-2}$. Taking a path $P_3$ from $\mbox{cutv}(E)$ to $b$ in $G_b$ we have constructed a path $P=P_1p(x)xP_2P_3$ from $a$ to $b$ of length at least $2^{d-1}$, a contradiction. 

If $G_b$ is 2-connected then the same proof as in (i) shows that $G_b$ must contain two exit vertices one of which $x$ has $x\neq b$ and $p(x) \neq a$. By induction on $d$ we obtain endblock paths from $a$ to $p(x)$ in $G_a$ and from $x$ to $b$ in $G_b$ both of length at least $2^{d-2}$. Joining the two with edge $xp(x)$, $G$ contains the required path, a contradiction.

(iii)
Suppose $a$ did lie in the interior of an endblock $E$ of $G_a$. As $d_{G_a}(a)\geq 2$ $E$ is 2-connected, so by induction on $d$ we have an endblock path $P_1$ from $a$ to $\mbox{cutv}(E)$ in $G[E]$ of length at least $2^{d-2}$. Now by (ii) $G_a$ is not 2-connected and so it contains a second endblock $E'$, with an exit vertex $x$. Again by induction on $d$, $G[E']$ contains an endblock path $P_3$ from $\mbox{cutv}(E')$ to $x$ of length $2^{d-2}$. Join $\mbox{cutv}(E)$ to $\mbox{cutv}(E')$ by a path $P_2$ in $G_a$ and $p(x)$ to $b$ by a path $P_4$ in $G_b$. Combining all of these paths we have a path $P_1P_2P_3xp(x)P_4$ from $a$ to $b$ of length at least $2^{d-1}$, a contradiction.

(iv)
This follows from (ii) and (iii) as if $G_a$ is not 2-connected and $a$ does not lie in the interior of any endblock, $a$ must have at least two limbs.
}
\end{proof}

\begin{figure}
\centering
\input{List.pstex_t}
\caption{Path $P$ constructed in Lemma \ref{list}(ii). Curved paths like $P_1$ and $P_2$ will represent endblock paths of length at least $2^{d-2}$ throughout.}
\end{figure}


Note that by symmetry of $a$ and $b$, Lemma \ref{list} also applies on replacing $a$ with $b$. The next proposition dispenses with the simplest case we can use endblock paths to build our path of length $2^{d-1}$ from $a$ to $b$.

\begin{prop} 
{
\label{int}
For an exit vertex $x$ in an endblock $E$ of $G_a$, $p(x)$ can never lie in the interior of an endblock $F$ of $G_b$.
}
\end{prop}

\begin{proof}
{
From Lemma \ref{list}(iii) $a\notin \mbox{int}(E)$ and $b\notin \mbox{int}(F)$. Pick a path $P_1$ in $G_a$ from $a$ to $\mbox{cutv}(E)$ and a path $P_4$ in $G_b$ from $\mbox{cutv}(F)$ to $b$. Since $E$ is 2-connected and all $v\in E-\lbrace \mbox{cutv}(E),x\rbrace $ have degree at least $d-1$ in $G[E]$, by induction $G[E]$ contains a path $P_2$ of length at least $2^{d-2}$ from $\mbox{cutv}(E)$ to $x$. Similarly $G[F]$ contains a path $P_3$ of length at least $2^{d-2}$ from $p(x)$ to $\mbox{cutv}(F)$. Combining these gives an $a-b$ path $P=P_1P_2xp(x)P_3P_4$ of length at least $2^{d-1}$, a contradiction.
}
\end{proof}






























\section{The Interaction Digraph}

Let $K_1,\ldots ,K_r$ be the limbs of $a$ and $L_1,\ldots ,L_s$ be the limbs of $b$. Note that by Lemma \ref{list}(iv) $r,s\geq 2$.

We form an auxiliary bipartite multidigraph $H=(A,B,\overrightarrow {E})$ which will represent the interaction between the limbs and cores of $a$ and $b$. Let $A=\lbrace {K_1,\ldots ,K_r }\rbrace $ and $B=\lbrace {L_1,\ldots ,L_s }\rbrace $. Additionally, adjoin $\mbox {Core}(a)$ to $A$ and $\mbox {Core}(b)$ to $B$ if they are non-empty. Given an endblock $E$ of $G_a$ there exists an exit vertex $x$ with $x\neq a$ and $p(x)\neq b$ by Lemma \ref{list}(i) and (iii). Pick exactly one such exit vertex $x_E$ for each such endblock $E$ and adjoin a directed edge to $H$ from $K$ to $W\in B$ where $E$ is contained in limb $K$ and $p(x_E)\in W$. Similarly, for each endblock $F$ in $L$ we pick an exit vertex $y_F\in F$ with $p(y_F) \neq a$ and add a directed edge to $H$ from $L$ to $V$ where $p(y_F)\in V$. 

Note that by Proposition \ref{int} we never choose an exit vertex $x_E$ for some $E$ and $y_F$ for some $F$ such that $p(x_E)=y_F$. Also since any limb of $a$ or $b$ contains an endblock, every limb vertex in $H$ must have outdegree at least one and core vertices have no outneighbours. 

We shall study the component structure of $H$. The next two lemmas say that this must be very restricted. Together they will allow us to find a connected component $C$ of $H$ consisting entirely of limbs. The inductive step in Section 5 will take place on the subgraph of $G$ corresponding to this $C$.

\begin{lem}
{
\label{paths3}
$H$ cannot contain an undirected path of length three.
}
\end{lem}

\begin{proof}
{
Suppose we have such an undirected path $Q=V_0V_1V_2V_3$ in $H$ and assume $V_0\in A$. Each directed edge $\overrightarrow {VW}$ of $Q$ gives an endblock in $V$ with exit vertex $x$, such that $p(x)\neq b$ and $p(x)\in W$. These endblocks are distinct by the construction of $H$ and in each we can find an endblock path of length $2^{d-2}$ from its cutvertex to this exit vertex by induction on $d$. We claim that we can form an $a-b$ path $P$ which extends all three of these paths. As such a path has length at least $3(2^{d-2})>2^{d-1}$, this contradicts our choice of $G$ and proves the lemma.

We will construct our path by forming paths $P_i$ in each $V_i$ and eventually join them into one. The start point of $P_i$ will be denoted by $a_i$ and its end point by $b_i$. We first choose these vertices.

If $\overrightarrow {V_iV_{i+1}}$ is an edge of $Q$ there is an endblock $E$ in $V_i$ with an exit vertex $x$ such that $p(x)\in V_{i+1}$. In this case let $b_i=x$ and $a_{i+1}=p(x)$. If $\overleftarrow {V_iV_{i+1}}$ is an edge of $Q$ this gives an endblock $E$ in $V_{i+1}$ with an exit vertex $x$ such that $p(x)\in V_{i}$. In this case let $b_i=p(x)$ and $a_{i+1}=x$. We set
\[a_0 = \left\{ \begin{array}{ll}
         \mbox{Joint$(V_0)$} & \mbox{if $V_0$ is a limb of $a$};\\
        b_0 & \mbox{if $V_0=$Core$(a)$}\end{array} \right. \]
\[b_3 = \left\{ \begin{array}{ll}
         \mbox{Joint$(V_3)$} & \mbox{if $V_3$ is a limb of $b$};\\
        a_3 & \mbox{if $V_3=$Core$(b)$}.\end{array} \right. \] 

\noindent Note that $b_i$ and $a_{i+1}$ are adjacent for $i\in \lbrace 0,1,2\rbrace $ and $a,b\notin \{b_0,a_1,b_1,a_2,b_2,a_3\}$. 

We now build the paths $P_i$ from $a_i$ to $b_i$ in each $V_i$, where $V_i$ is a limb. We claim we can choose $P_i$ so that neither $a$ nor $b$ are interior vertices of $P_i$ (that is, they can lie on $P_i$, but only as end vertices) and $P_i$ has length at least $2^{d-2}$ if $V_i$ has one outneighbour on $Q$ and $2^{d-1}$ if $V_i$ has two. Indeed, if $V_i$ has one outneighbour in $Q$ then one of $a_i$ or $b_i$ must be an exit vertex of an endblock $E$ of $V_i$. Without loss of generality this is $a_i$. Then $b_i\notin \mbox{int}(E)$ by Proposition \ref{int} and $G\lbrack E\rbrack $ contains a path of length $2^{d-2}$ from $a_i$ to the cutv$(E)$. Since $V_i-\lbrace a,b\rbrace $ is connected for all $i$ from the definition of a limb, we can extend this path from cutv$(E)$ to $b_i$ as required. The case where $V_i$ has two outneighbours on $Q$ is identical, using the same argument in two endblocks of $V_i$ and joining their cutvertices in $V_i$.

Finally we combine the $P_i$ paths. We first deal with the case where neither Core$(a)$ nor Core$(b)$ occur as interior vertices of $Q$. Combining the paths above we have an $a_0-b_3$ path $P'=P_0b_0a_1P_1b_1a_2P_2b_2a_3P_3$. If $\mbox{Body}(a)=\lbrace a\rbrace $ then $P'$ starts at $a$ so we only need to extend $P'$ to start at $a$ when 
$\mbox{Body}(a)\neq \lbrace a\rbrace $. In $P'$ as constructed above, $\mbox {Body}(a)\cap P'$ contains $a_0$ and at most one other vertex. Since $\mbox{Body}(a)$ is 2-connected it contains a path $P_1'$ from $a$ to $a_0$ avoiding this vertex. Finding a similar path $P_2'$ from $b_3$ to $b$ in $\mbox {Body}(b)$ if $\mbox {Body}(b)\neq \lbrace b\rbrace $ we may take $P=P_1'P'P_2'$.


\begin{figure}
	\centering
	\input{Paths3.pstex_t}
	\caption{An illustration of Lemma \ref{paths3} in the case where $V_2=\mbox{Core}(a)$ and $V_0V_1$, $V_1V_2$ and $V_3V_2$ are directed edges of $Q$. As in the proof of Lemma \ref{paths3}, 2-connectivity can be used in $\mbox{Body}(a)$ to find vertex disjoint paths from $\{a_0,a_2\}$ to $\{b,b_2\}$.}
\label{picpaths3}
\end{figure}


If $Q$ contains one of the Core vertices, without loss of generality let it be Core$(a)$. If Core$(a)$ occurs as an interior vertex of $Q$, it must be $V_2$. Body$(a)$ then contains distinct $a_0,a_2,b_2$ and we have two paths $P_1'=P_0b_0a_1P_1b_1a_2$ from $a_0$ to $a_2$ and $P_2'=b_2a_3P_3$ from $b_2$ to $b_3$ as in Figure \ref{picpaths3}. From the choice of the $a_2$ and $b_2$ above and the fact that $a$ is not a cutvertex we have $a\notin \lbrace a_0,a_2,b_2\rbrace $. Then by 2-connectivity Body$(a)$ contains two vertex disjoint paths from $\lbrace a_0,a_2\rbrace $ to $\lbrace a,b_2\rbrace $. Piecing these paths together with $P_1'$ and $P_2'$ we obtain an $ab_3$-path $P'$. If Body$(b)=\lbrace b\rbrace $ we are done since $b=b_3$. Otherwise we extend $P'$ using 2-connectivity as above to find an $a-b$ path of length at least $2^{d-1}$, a contradiction to the choice of $G$.
}
\end{proof}




Note that Lemma \ref{paths3} guarantees that $H$ has at least two connected components. The next lemma further limits $H$. Its proof is very similar to that of Lemma \ref{paths3}.

\begin{lem} 
{
\label{body}
Suppose that we have $\mbox{Body}(a)\neq \lbrace a\rbrace $. Then no component of $H$ contains two vertices of $A$.
}
\end{lem}

\begin{proof}
{
Suppose $H$ has such a component $C$. Then by Lemma \ref{paths3}, $C$ consists of vertices $V_1,\ldots ,V_t$ in $A$ and vertex $W$ in $B$. At most one of $V_1,\ldots ,V_t, W$ can be a core vertex as there is no edge between Core$(a)$ and Core$(b)$ in $H$. 

If $W=\mbox{Core}(b)$ then $V_1$ and $V_2$ must be limbs and these guarantee two vertex disjoint paths $P_1$, $P_2$ from vertices $a_1,a_2\in \mbox{Body}(a)$ to vertices $b_1,b_2\in \mbox{Body}(b)$ both of length at least $2^{d-2}$. By Lemma \ref{paths3} and Lemma \ref{list}(iv) $H$ must contain a second component $C'$ containing a limb of $b$ which guarantees the existence of a third path $P_3$ from a vertex $a_3\in \mbox{Body}(a)$ to $b_3\in \mbox{Body}(b)$ of length $2^{d-2}$. Using identical 2-connectivity arguments in both $\mbox{Body}(a)$ and $\mbox{Body}(b)$ as in Lemma \ref{paths3} we can combine these three paths into one from $a$ to $b$, a contradiction.

If $W\neq \mbox{Core}(b)$ then $C$ guarantees a path $P_1$ of length $2^{d-1}$ between two vertices $a_1$ and $a_2$ in $\mbox{Body}(a)$ with $b\notin P_1\cap \mbox{Body}(b)$ and  $|P_1\cap \mbox{Body}(b)|\leq 1$. Again from a second connected component of $H$ we obtain a disjoint path $P_2$ from an element $a_3\in \mbox{Body}(a)$ to $b_1\in \mbox{Body}(b)$. Once more, with an application of 2-connectivity in $\mbox{Body}(a)$ and a possible application in $\mbox{Body}(b)$ we find an $a-b$ path extending both $P_1$ and $P_2$, a contradiction.
}
\end{proof}





Again the same applies switching $a$ with $b$. As mentioned before Lemma \ref{paths3} the previous two lemmas imply that $H$ contains a connected component $C$ consisting entirely of limbs. If not, each component of $H$ would contain one of Core$(a$) or Core$(b)$ and thus $H$ would contain at most two connected components. Since $H$ contains no path of length 3 by Lemma \ref{paths3}, it must have exactly two components, one containing Core$(a)$ and the other containing Core$(b)$. But as $A$ contains Core$(a)$ and at least two limbs, two of these must lie in the same connected component contradicting Lemma \ref{body}.



























































\section {The Inductive Step}

Let ${C}$ be the component of $H$ consisting entirely of limbs of $a$ and $b$ guaranteed from Section 4 and write $G_C$ for the subgraph $G[\bigcup _{W\in C}V(W)]$ of $G$. Notice that $G_{C}$ must contain exactly one vertex $a_C$ in $\mbox{Body}(a)$ and one vertex $b_C$ in $\mbox{Body}(b)$ - if Body$(a)= \lbrace a\rbrace$ then $a_C=a$, if not ${C}\cap A=\lbrace V\rbrace $ by Lemma \ref{body} and $a_C=\mbox{Joint}(V)$.

Our final lemma before we complete the proof of Theorem 2.3$'$ allows us to find a subgraph of $G_C$ which will either also satisfy the conditions of Theorem \ref{connmod} or build at least half of the path we are looking for from any edge entering it. Before stating it we give one last definition.

\begin{dfn}
{
\emph{Given a graph $G$ and $S\subset V(G)$ define the span$(S)$ in $G$ to be the subset of $V(G)$ consisting of all vertices which lie on a path between two elements of $S$.}
}
\end{dfn}

Note that we include paths of length zero in this definition, so that $S\subset $ span($S$).

\begin{lem}
{
\label{nice}
Let $C$ and $G_C$ be as above. Then $G_C$ has a 2-connected subgraph $J$ containing two vertices $a'\in G_a$ and $b'\in G_b$ with the following properties:
\begin{itemize}
{
\item[\emph{(i)}] every vertex $v\in J - \lbrace a',b'\rbrace$ has degree at least $d-1$ in $J$ and all the neighbours of $v$ in $G_C$ are contained in $J$.

\item[\emph{(ii)}] for any vertex $v\in J-\lbrace a',b'\rbrace $, $J$ contains an $a'-v$ path not containing $b$ and a $b'-v$ path not containing $a$, both of length at least $2^{d-2}$.
}
\end{itemize}
}
\end{lem}

\begin{proof}
{
Suppose first that $C$ consists of two vertices with a limb $K$ in $A\cap C$ and $L$ in $B\cap C$. Let $S$ be the subset of vertices of $K-a$ with a neighbour in $L-b$ and $T$ the subset of $L-b$ with a neighbour in $K-a$. Note that by definition of $C$ each endblock in $K$ has an exit vertex $x$ with $p(x)\in L-a$ and by Proposition \ref{int} $p(x)$ cannot lie in the interior of an endblock of $L$. As the same holds true for the endblocks in $L$, both $|S|,|T|\geq 2$. 


Consider the graph $G' = G[\mbox{span}(S)\cup \mbox{span}(T)]$. This is 2-connected and contains all vertices of the endblocks of $K$ in $G_a$ and $L$ in $G_b$. Furthermore, $G'$ restricted to $G_a$ is a union of blocks of $G_a$. Such a subgraph must be joined to the rest of the $G_a$ by a single cutvertex $a_0'$. The same holds true for $G'$ restricted to $G_b$ with cutvertex $b_0'$. While this is almost the graph we will take as $J$, $a$ and $b$ may be vertices of $K$ and $L$ respectively, not lie in $G'$ but still have a neighbour in $G'-\lbrace a_0',b_0'\rbrace $ which would not allow (i) to hold. If this occurs with $a$ say, then adjoin it to $S$ and run the same construction as above with this new $S$ to obtain a new graph $G''$. Let the $a_1'$ be the cutvertex with the rest of $G_a$ and $b_1'$ the cutvertex with the rest of $G_b$. The same problem may now occur with with $G''$ and $b$. If so, adjoining $b$ to $T$ we obtain our final graph $G'''$, which again is 2-connected with cutvertex $a_2'$ with the rest of $G_a$ and cutvertex $b_2'$ with the rest of $G_b$. It should be clear that (i) now certainly holds for this graph and we may take $J=G'''$, $a'=a_2'$ and $b'=b_2'$.


To see that $J$ contains an $a'-v$ path as claimed in (ii) we first consider the case with $b'\neq b$. Now $J$ contains an endblock $E$ from $G_a$ and an endblock $F$ from $G_b$ and as $v$ is in at most one of these, assume $v\notin F$. Taking $\widetilde {J}$ to be the graph formed from $J$ by contracting int$(F)$ to a single point $f$ it is easily seen $\widetilde {J}$ is still 2-connected. As neither $a'$ nor $b'$ can lie in the interior of $F$, by 2-connectivity $\widetilde{J}$ contains two vertex disjoint paths from the set $\lbrace a',v\rbrace $ to $\lbrace {\mbox{cutv}(F), f} \rbrace $. These paths give two paths in $J$, $P_1$ from $a'$ to say $w\in \mbox{int}(F)$ and $P_3$ from $v$ to $\mbox{cutv}(F)$. By induction on Theorem \ref{connmod} $G[F]$ contains a path $P_2$ of length $2^{d-2}$ from $\mbox{cutv}(F)$ to $w$. $P=P_1P_2P_3$ now works for the $a'-v$ path claimed in (ii).

If $b'=b$, using the same argument as above we might use $b$ in one of the paths $P_1$ or $P_3$. However in this case we have the following:
\begin{quotation}
{
\noindent $J-b$ has a 2-connected subgraph $J'$ containing all of $J\cap G_a$ and an endblock of $G_b$. 
}
\end{quotation}
To see this, look at the block-cutvertex decomposition of $J-b$. This contains exactly one block $J'$ with vertices in both $G_a$ and $G_b$ and this block contains all of $J\cap G_a$ by construction. Since any endblock of $G_b$ contained in $J$ has an exit vertex whose partner lies in $J\cap G_a$, all such endblocks lie in $J'$. Given $v$ as above, choose a minimal path $P_0$ not containing $b$ from $v$ to some $v'\in J'$. We may now run the same argument as above in $J'$ to obtain a $a'-v'$ path $P'$ of length at least $2^{d-2}$. Combining the resulting path with $P_0$ we are done. By symmetry this finishes the case where $C$ consists of two vertices.







We now deal with the case where $C$ consists of more than two vertices. By Lemma \ref{paths3} and Lemma \ref{body} we may assume $C$ consists of a limb $K$ of $a$, limbs $L_1,\ldots L_t$ of $b$ and that Body$(b)=\lbrace b\rbrace $. Let $L_1,\ldots ,L_{t'}$, $t'\leq t$, be the limbs containing at least two vertices other than $b$ with neighbours in $K-a$. Note that $t'\geq 1$ since some $L_i$ must be an outneighbour of $K$ in $H$. We will first work with these limbs and add in the rest if needed later. 

As above, for each $i\in \lbrack 1,t'\rbrack $ let $S_i\subset V(K)$ consist of those vertices in $K-a$ with a neighbour in $L_i-b$ and $T_i\subset V(L_i)$ consist of the vertices of $L_i-b$ with a neighbour in $K-a$. Taking $G_i=G\lbrack \mbox{span}(S_i)\cup \mbox{span}(T_i)\rbrack $ this graph is 2-connected for all $i\in \lbrack 1,t'\rbrack $. Note that $G_i\cap G_b$ must again have exactly one cutvertex with the rest of $G_b$, say $c_i$. Once more there are concerns that $a\in K$ or $b\in L_i$ are not contained in $G_i$ but have neighbours in it as this would violate (i) above. We will again adjoin them to $S_i$ and $T_i$ as needed. While the condition to adjoin $a$ to $S_i$ is exactly the same as above, that is adjoin $a$ to $S_i$ if $a$ has a neighbour in $G_i\cap G_b-c_i$, the condition to adjoin $b$ to $T_i$ needs a slight variation since $G_i\cap G_a$ may have more than one cutvertex separating it from the rest of $G_a$. With a little foresight, take $c_i'\in G_i\cap G_a$ to be the unique cutvertex of $G_a$ separating $G_i\cap G_a$ from $a$ (possibly $a$ itself) and adjoin $b$ to $T_i$ if $b$ has a neighbour in $G_i\cap G_a-c_i'$. For each $i\in[ 1,t'] $, having added the vertices to $S_i$ and $T_i$ as demanded by these conditions, let $S_i$ and $T_i$ now refer to the new sets and $G_i$ to the new graphs formed from them.

For all $M\subset \lbrack 1,t\rbrack $ define $S_M=\bigcup _{j\in M}S_j$. Beginning with an initial list $\lbrace S_1,\ldots ,S_{t'}\rbrace $ repeatedly remove $S_M$ and $S_{N}$ from the list and adjoin $S_{M\cup {N}}$ if $|\mbox {span}(S_M)\cap \mbox {span}(S_{N})|\geq 2$. This procedure eventually terminates, and in the final list there must exist some $S_M$ for which $G[\mbox{span}(S_M)]$ has a single cutvertex separating it from the rest of $G_a$. To see this note that for each $I$, $G[\mbox{span}(S_I)]$ is a connected union of blocks of $G_a$ and so corresponds to a subtree of the block graph $\mathcal{B}(G_a)$. Since each leaf of $\mathcal{B}(G_a)$ is contained in some $G[\mbox{span}(S_I)]$ and no two $G[\mbox{span}(S_I)]$ and $G[\mbox{span}(S_{I'})]$ share a block, one of these, $G[\mbox{span}(S_M)]$ say, must have a single cutvertex $a'$ with the rest of $G_a$. 

Now we deal with the limbs $L_j$ where $j\in \lbrack t'+1,t\rbrack $. Form a set $N\subset \lbrack t'+1,t\rbrack $ with $i\in N$ if some $v\in L_i-b$ has a neighbour in $\mbox{span}(S_{M})-a'$ and let $I=M\cup N$. 

If $I=\lbrace i\rbrace$ for some $i$ then $N=\emptyset $ and we can run the same argument as in the case where $C$ consists of two vertices replacing $S$ with $S_i$ and $T$ with $T_i$. If not, take $J=G[\bigcup _{i\in I} V(L_i) \cup \mbox{span}(S_I)]$. $J$ is 2-connected and taking $b'=b$, $J$ satisfies (i).
 
Finally we show that (ii) holds for $J$. Given $v\in J-\lbrace a',b'\rbrace $ suppose we are looking for an $a'-v$ path avoiding $b$ of length at least $2^{d-2}$. We again claim:
\begin{quotation}
{
\noindent $J-b$ has a 2-connected subgraph containing all of $J\cap G_a$ and an endblock $F$ of $G_b$.
}
\end{quotation}

It suffices to show that $G[\bigcup _{i\in M}V(L_i)\cup \mbox{span}(S_{M})]$ contains such a subgraph. Exactly as in the case where $C$ consists of two limbs, each $G[\mbox{span}(S_i)\cup \mbox{span}(T_i)]-b$, $i \in [1,t']$, has a 2-connected subgraph $G_i'$ containing all of $\mbox{span}(S_i)$. Moreover one of the subgraphs $G[\mbox{span}(T_i)]-b$ must contain an entire endblock $F$ (since $t'\geq 1$). Now the subgraph $G[\bigcup _{i\in M}V(G_{i}')]$ of $J-b$ is 2-connected by construction of $M$, contains all vertices of $J\cap G_a$ and endblock $F$ in $G_b$, proving the claim. Using this subgraph, exactly as in the case where $C$ consists of two limbs, we obtain an $a'-v$ path of desired length. 

An identical argument gives the $b'-v$ path as claimed in (ii).
}
\end{proof}

\begin{figure}
\centering
\input{together.pstex_t}
\caption{An illustration of the case $w\in \mbox{int}(E)$ in the proof of Theorem 2.3$'$. The broken dotted pieces represent vertices in $G_C$ that are left out of $J$.}
\label{together}
\end{figure}

Now we are ready to finish the proof of Theorem 2.3$'$. Let $J$ be the subgraph of $G$ guaranteed from Lemma \ref{nice}. If there is no edge between $J-\lbrace a',b'\rbrace $ and $G-J$, all $v\in J-\lbrace a',b'\rbrace $ have degree at least $d$ in $J$ and by choice of $G$, $J$ contains an $a'-b'$ path $P$ of length at least $2^{d-1}$. Extending this path from $a'$ to $a$ and $b'$ to $b$, $G$ contains an $a-b$ path of length $2^{d-1}$, a contradiction. 

So such an edge must exist, joining say $v\in J-\lbrace {a',b'}\rbrace $ to $w\notin G_C$ by Lemma \ref{nice}(i). We may assume $w\in G_a$. First suppose $w\in \mbox{Body}(a)$ -- this is only possible if $\mbox{Body}(a)\neq \{a\}$, by Lemma \ref{nice}(i). Applying Lemma \ref{nice}(ii) we have an $a'-v$ path in $J$ not containing $b$ of length at least $2^{d-2}$. This path extends in $C$ to an $a_C-v$ path $P_1$, where again $a_C=G_C\cap \mbox{Body}(a)$. Now taking a limb $K$ of $a$ not in $C$, $K$ guarantees a path $P_2$ from Joint$(K)$ to $b$ of length at least $2^{d-2}$ disjoint from $P_1$. Thus we have a path $P_1vw$ joining two vertices $a_C$ and $w$ in Body$(a)$ and a path $P_2$ from Joint$(K)$ to $b$. By 2-connectivity, Body$(a)$ 
contains two vertex disjoint paths $P_3$ and $P_4$ from $\lbrace a, \mbox{Joint}(K)\rbrace $ to $\lbrace a_C,w\rbrace $. Combining all four of these paths we obtain an $a-b$ path $P$ extending both $P_1$ and $P_2$. But this path has length at least $2^{d-1}$, contradicting our choice of $G$.

So we may assume $w\notin $ Body$(a)$. Then $w\in K$ for some limb $K$ of $a$, where by Lemma \ref{nice}(i) $K\notin C$. Let $E$ be an endblock of $K$ and take $x_E$ to be the exit vertex of $E$ chosen in the construction of $H$ in Section 4. Note that $p(x_E)\notin G_C$, since $K\notin C$. Depending on whether or not $w$ lies in int$(E)$ we can construct a path $P$ from $w$ to either Joint$(K)$ or to $x$ of length $2^{d-2}$ by induction on $d$ in Theorem \ref{connmod}. If $P$ is from $w$ to Joint$(K)$ adjoin it via the edge $vw$ to the $v-b'$ path in $J$ guaranteed by Lemma \ref{nice}(ii) (see Figure \ref{together}). This gives a Joint$(K)-b'$ path $P'$ of length at least $2^{d-1}$ which extends to an $a-b$ path. If $P$ is from $w$ to $x_E$ then we combine this path with the $v-a'$ path in $J$ guaranteed by Lemma \ref{nice}(ii). Again this gives a $a'-p(x_E)$ path of length at least $2^{d-1}$ which extends to an $a-b$ path. This proves Theorem 2.3$'$. \hspace{5cm} $\square$




















\section{Removing the Degree Assumption}


Recall in Lemma \ref{splitting}, we obtained a splitting of $G$ into two pieces, one containing $a$ and the other containing $b$ by choosing a direction $i$ on which $a$ and $b$ differ when viewed as elements of $\mathcal{P}[n]$. In general it is not possible to choose such a direction to ensure that both $d_{G_a}(a)\geq 2$ and $d_{G_b}(b)\geq 2$ -- for example, $a$ and $b$ could be adjacent with both having only one other neighbour in $G$. It is however always possible to choose such a direction $i$ if $d_G(a)\geq 3$ and $d_G(b)\geq 3$. We will therefore assume that $d_G(a)=2$.

The condition $d_{G_a}(a)\geq 2$ and $d_{G_b}(a)\geq 2$ as used above allowed us to ensure that all endblocks of $G_a$ and $G_b$ contain long paths, which is clearly false if $a$ has a single neighbour $a'$ in $G_a$. This in turn guaranteed that $a$ had at least two limbs in $G_a$ which was crucially used numerous times in our analysis of $H$ e.g. Lemma \ref{body}. In this section, we extend the arguments of Theorem 2.3$'$ to prove Theorem \ref{connmod}. 


\begin{lem} 
\label{remove}
The following hold:
\begin{itemize}
{
\item[\emph{(i)}] $G-a$ is a 2-connected graph.

\item[\emph{(ii)}] We can choose a splitting direction $i$ such that after forming $G_a$ and $G_b$ as above from this $i$, $d_{G_a}(a)\geq 2$ or $d_{G_b}(b)\geq 2$
}
\end{itemize}
\end{lem}

\begin{proof}
 {

(i) If $G-a$ is not 2-connected it has at least two endblocks in its block-cutvertex decomposition, one of which $E$ has $b\notin \mbox{int}(E)$. Now since $G$ is 2-connected, $a$ must be joined to the interior of all the endblocks of $G-a$. As $d_G(a)=2$, $G-a$ has exactly two endblocks with $a$ having exactly one neighbour in the interior of each. Let $w$ be this neighbour in $E$.

Now $E$ is 2-connected (as $d\geq 3$) and all vertices in $G[E]-\lbrace \mbox{cutv}(E), w\rbrace $ have degree at least $d$ in $G[E]$. Since $G$ is the smallest counterexample and $G[E]$ is a non-spanning subgraph of $G$, it contains a path $P$ of length $2^{d-1}$ from $w$ to $\mbox{cutv}(E)$. Extending this path on either side to $a$ and $b$ respectively, we have an $a-b$ path of length at least $2^{d-1}$, a contradiction.

(ii) We can always choose such a direction if $a$ and $b$ are at Hamming distance at least three in $Q_n$ or if one of $a$ or $b$ have degree greater than 2 in $G$. So $a$ and $b$ must be at Hamming distance one or two in $G$ and both have degree exactly two. 

First consider $a$ and $b$ at Hamming distance one. If they are not adjacent in $G$ we may choose the direction on which they differ for $i$ so we can assume they are adjacent. Then $a$ and $b$ both have one other neighbour in $G$, $a'$ and $b'$ respectively. Now if $G-\{a,b\}$ is 2-connected we can apply Theorem \ref{connmod} to $G-\{a,b\}$ with $a'$ and $b'$ replacing $a$ and $b$ to obtain an $a'-b'$ path of length at least $2^{d-1}$. Adjoining the edges $aa'$ and $bb'$ to this path we have an $a-b$ path of length $2^{d-1}+2$, more than enough. If $G-\{a,b\}$ is not 2-connected it is easily seen that $a'$ and $b'$ must lie in the interior of different endblocks of $G-\{a,b\}$. We can therefore find a path from $a'$ to $b'$ in $G-\{a,b\}$ which extends two endblock paths. Adjoining the edges $aa'$ and $bb'$ to this path again we have an $a-b$ path of length at least $2^{d}+2$.

If $a$ and $b$ are at Hamming distance two in the cube, we can always find such a direction $i$ unless $a$ and $b$ are joined to the same two neighbours in $G$, $a'$ and $b'$ say. Then $\lbrace a,a',b,b'\rbrace $ form a $C_4$ with $a$ opposite $b$. Working with $G-\lbrace a,b\rbrace $, $a'$ and $b'$ as above, we again obtain an $a-b$ path of desired length in $G$.
}
\end{proof}


From Lemma \ref{remove}(ii) we can now assume that we have chosen a partition direction $i$ such that $\mbox{deg}_{G_b}(b)\geq 2$. Lemma \ref{list}(i)-(iv) still hold for $G_b$ with the same proofs as above. In particular $b$ has at least two limbs. In order for our main argument in Theorem 2.3$'$ to be inapplicable, $a$ must have exactly one neighbour $a'$ in $G_a$ and one neighbour $v$ in $G_b$. We may also assume that $v\neq b$ as otherwise by Lemma \ref{remove}(i) we could apply Theorem \ref{connmod} to $G-a$ taking $a'$ in place of $a$. 

\begin{lem}
{
\label{pick}
 We have $v\in \mbox{int}(E_v)$ for some endblock $E_v$ of $G_b$. 
}
\end{lem}

\begin{proof}
{
Suppose not. From Lemma \ref{list}(iii) $b$ does not lie in the interior of an endblock of $G_b$ and by Lemma \ref{list}(iv) $G_b$ contains two vertex disjoint paths $P_1$ from $v$ to $\mbox{cutv}(E_1)$ and $P_5$ from $\mbox{cutv}(E_2)$ to $b$, where $E_1$ and $E_2$ are two endblocks of $G_b$. Taking exit vertices $x_1$ and $x_2$ of $E_1$ and $E_2$ respectively, by induction on $d$, $G[E_1]$ contains a path $P_2$ of length at least $2^{d-2}$ from $\mbox{cutv}(E_1)$ to $x_1$ and $G[E_2]$ contains a path $P_4$ of length at least $2^{d-2}$ from $x_2$ to $\mbox{cutv}(E_2)$. Taking a path $P_3$ from $p(x_1)$ to $p(x_2)$ in $G_a-a$ and combining the paths, $G$ contains an $a-b$ path $avP_1P_2x_1p(x_1)P_3p(x_2)x_2P_4P_5$ of length at least $2^{d-1}$, a contradiction.
}
\end{proof}

We again construct an interaction digraph $H$ but this time it is built from the limbs of $a'$ and $b$ instead of those of $a$ and $b$. Note that $\{a,a'\}$ is a limb of $a'$ and so both $a'$ and $b$ have at least two limbs. Take $H=(A',B,\overrightarrow{E})$ to be a bipartite multidigraph on vertex sets $A'=\{K_1,\ldots ,K_r\}$ and $B=\{L_1,\ldots L_s\}$, the set of limbs of $a'$ and $b$ respectively. We also adjoin $\mbox{Core}(b)$ to $B$ if it is non-empty ($\mbox{Core}(a')=\emptyset$ since $a'$ is a cutvertex of $G_a$). Now each endblock of $G_a$ or other than $\{a,a'\}$ contains at least two exit vertices, as in Lemma \ref{list}(i). Therefore for each endblock $E$ of $G_a$ or $G_b$ other than $\{a,a'\}$ we can pick an exit vertex $x_E$ with $p(x_E)\neq a',b$. From Lemma \ref{pick} we can pick $x_{E_v}=v$. Now adjoin a directed edge from $K\in A'$ to $L\in B$ for each endblock $E$ in $K$ with $p(x_E)\in L$ and a directed edge from $L\in B$ to $K\in A'$ for each endblock $E$ in $L$ with $p(x_E)\in K$. Note that every limb other than $\{a,a'\}$ still has an outneighbour in $H$. 

For this $H$ Lemma \ref{paths3} and Lemma \ref{body} still hold with the same proofs as before. These two ensure that $H$ still contains a connected component $C$ consisting entirely of limbs and not containing the limb $\{a,a'\}$. Indeed, since $b$ has at least two limbs, pick a limb $L\in B$ not containing $E_v$ and let $C$ be the connected component of $H$ with $L\in C$. As $v$ is the unique neighbour of $a$ in $B$ and $v\notin L$, if $\{a,a'\}\in C$ then $H$ would contain a path of length three, contradicting Lemma \ref{paths3}. Furthermore, since $\mbox{Core}(a')\notin A'$, if $C$ did not consist entirely of limbs of $a'$ and $b$, $\mbox{Body}(b)\neq \{b\}$ and $C$ contains two vertices of $B$, contradicting Lemma \ref{body}. Following the argument as in Section 5, an application of Lemma \ref{nice} to $G_C$ finishes the proof of Theorem \ref{connmod}. \hspace{5cm} $\square$





























\section {A Tight Bound}

Theorem \ref{conn} is proved in the exact same manner as Theorem \ref{connmod} but requires a more care and attention to detail in various arguments. 
We are now ready for its proof.
\vspace{0.3cm}

\noindent \emph{Proof of Theorem \ref{conn}.} The proof is again by induction on $d$. The base case $d=2$ is immediate unless $a$ and $b$ are at Hamming distance 2 apart. If this is the case and $G$ is not isomorphic to $Q_2$ pick any vertex $v$ of $G$ not in the unique 2-cube containing $a$ and $b$. By 2-connectivity $G$ contains vertex disjoint $a-v$ and $v-b$ paths, which when combined give a path of length at least 3, as required. Suppose for contradiction that Theorem \ref{conn} fails for some minimal $d$ and that $G$ is the smallest counterexample. 

We now explain how the proofs above in Sections 3-6 can be altered to give this stronger result. To begin we again assume there is some splitting direction $i$ of $G$ such that forming $G_a$ and $G_b$ as before, $d_{G_a}(a)\geq 2$ and $d_{G_b}(b)\geq 2$. The first lemma of this section says that Lemma \ref{list} still applies to $G_a$ and $G_b$.

\begin{lem}
{
\label{listextension}
\item[\emph{(i)}] Every endblock of $G_a$ which does not contain $a$ in its interior must contain at least two exit vertices.

\item[\emph{(ii)}] $G_a$ is not 2-connected.

\item[\emph{(iii)}] $a$ does not lie in the interior of an endblock in $G_a$.

\item[\emph{(iv)}] $a$ must have at least two limbs.
}
\end{lem}

\begin{proof}
 {

(i) The proof in this case needs only a slight variation, as if we apply our strengthened induction hypothesis to $E$ as Lemma \ref{list}(i), we are guaranteed to find an $a-x$ path of length at least $2^d-2$ and continuing this path as before we adjoin at least one more vertex $x$ with edge $xp(x)$ giving a bound of at least $2^d-1$, as required. 

(ii) The modification for the proof of this case is a little more demanding. Suppose for contradiction that $G_a$ is 2-connected.

First suppose $G_b$ is not 2-connected. If there exists an endblock $E$ in $G_b$ such that $b\notin E$, we have a path in $G_b$ of length at least 1 from $b$ to cutv($E$). We claim $E$ contains a cutv($E$)$-x$ path of length at least $2^{d-1}-1$ where $x$ is some exit vertex of $E$ with $p(x)\neq a$. If $E$ is isomorphic to the ($d-1$)-dimensional cube $Q_{d-1}$ every interior vertex of $E$ must be an exit vertex of $E$. Therefore we can take any $x\in \mbox{int}(E)$ with $p(x)\neq a$ at odd distance from $\mbox{cutv}(E)$. If $E$ is not isomorphic to the ($d-1$)-dimensional cube $Q_{d-1}$, by (i) $E$ must contain an exit vertex $x$ with $p(x)\neq a$ and by induction on Theorem \ref{conn} E contains a path of length $2^{d-1}-1$ from $\mbox{cutv}(E)$ to $x$. 

Combining the appropriate one of these two with the $a-p(x)$ path of length $2^{d-1}-2$ in $G_a$ guaranteed by induction on Theorem \ref{conn}, $G$ contains an $a-b$ path of length at least $1+(2^{d-1}-1)+1+(2^{d-1}-2)=2^d-1$ a contradiction. So $b$ must lie in \emph{every} endblock $E_1,\ldots ,E_t$ of $G_b$. Note that since $t\geq 2$ this implies $b\notin \mbox{int}(E_i)$ for any $i$. 

As with $E$ above, $E_1$ must have an exit vertex $x$ such that $E_1$ contains a $x-b$ path of length at least $2^{d-1}-1$, with $p(x)\neq a$. If $G_a$ were not isomorphic to $Q_{d-1}$, it contains a path of length $2^{d-1}-1$ from $a$ to $p(x)$. Combining these two with the edge $xp(x)$ we obtain an $a-b$ path of length $2^{d}-1$. Therefore we can assume $G_a$ is isomorphic to $Q_{d-1}$. For $t\geq 2$ none of the $E_1,\ldots ,E_t$ can be isomorphic to $Q_{d-1}$ as $G_a$ would have to receive too many edges. Now since $G_a$ is isomorphic to the cube, some endblock $E_i$ must contain an exit vertex $x$ with $p(x)\neq a$ such that $x$ is at even Hamming distance from $b$. But then since $E_i$ is not isomorphic to $Q_{d-1}$, by induction $E_i$ contains an $x-b$ path of length at least $2^{d-1}$. By induction on Theorem \ref{conn} applied to $G_a$, it contains an $a-p(x)$ path of length at least $2^{d-1}-2$. Combining these paths via the edge $xp(x)$ gives a desired path from $a$ to $b$ of length $2^d-1$. 

The case when $G_b$ is 2-connected is very similar. We can obtain two paths of length at least $2^{d-1}-1$ in $G_a$ and $G_b=E_1$ if neither of the two are isomorphic to $Q_{d-1}$ and if one is isomorphic to $Q_{d-1}$ we use the same argument as in the case where $G_a$ is isomorphic to $Q_{d-1}$ and $t\geq 2$ above.

(iii) This is similar to (ii) but a little easier. Again, taking the endblocks $E$ and $E'$ as in the proof of Lemma \ref{list}(iii), we can find a $a-\mbox{cutv}(E)$ path $P_1$ in $E$ of length at least $2^{d-1}-2$ and a $\mbox{cutv}(B)-x$ path $P_3$ in $E'$ of length at least $2^{d-1}-1$ where $x$ is an exit vertex of $E'$. Now if $p(x)=a$ then combining these we may only obtain an $a-b$ path of length $2^d-2$. Instead, using (i) we can choose the exit vertex $x$ so that $p(x)\neq a$. This gives the extra edge on the path required. 

(iv) Again follows from (ii) and (iii).
}
\end{proof}

\vspace{0.1cm}

The above modifications demonstrate the main problem moving from the bounds in Theorem \ref{connmod} to Theorem \ref{conn} -- 
on combining endblock paths together without any care as before, we are usually left short by one vertex. To get around this there are two small tricks, both of which were demonstrated above: we try to ensure that we form a path from $a$ to $b$ with at least two endblock paths, so that one of these paths has length at least $2^{d-1}-1$ and squeeze in another vertex on the way as in Lemma \ref{listextension}(iii) above or using a parity argument as in the case where $G_a$ is isomorphic to $Q_{d-1}$ we may be able to show that a given endblock $E$ which we know is not isomorphic to $Q_{d-1}$ contains an exit vertex at even distance away from its cutvertex. This second approach was used in Lemma \ref{listextension}(ii) and allows us to find an endblock path of length $2^{d-1}$ in $E$ which when combined with any other endblock path would give the required bound. 

As neither of these options can be guaranteed given the statement of Proposition \ref{int} we should not expect to be able to prove it.
Now Proposition \ref{int} was important in defining our interaction graph $H$ in Section 4 and 5. Can we find a way to define $H$ not depending on this?




We look towards an slightly altered construction for $H$. Note that unlike our first construction of $H$ in Section 4, since we cannot in general appeal to Proposition \ref{int}, we now have the possibility that an exit vertex of an endblock in $G_a$ is joined to an exit vertex of an endblock in $G_b$. It is necessary to pick these exit vertices $x_E$ such that $x_F\neq p(x_E)$ for every two endblocks $E$ and $F$ in $G_a$ and $G_b$ respectively in order to ensure that we can still find 2-connected subgraphs of $G$ in connected components of $H$ as in Lemma \ref{nice}. Can we always find such $x_E$ and $x_F$? 

The answer is that we can. For each endblock $E$ of $a$ or $b$, as was seen in Lemma \ref{listextension}(ii), there exists at least two exit vertices $x$ of $E$ such that $E$ contains a path of length at least $2^{d-1}-1$ from $\mbox{cutv}(E)$ to $x$.  We choose one of these for $x_E$ with the condition $p(x_E)\neq a,b$, which is always possible. What prevents us from choosing such an $x_E$ and $x_F$ with $x_F=p(x_E)$? Because joining the endblock paths from $\mbox{cutv}(E)$ to $x_E$ and the path from $x_F$ to $\mbox {cutv}(F)$ in $E$ and $F$ respectively, with the edge $x_Ex_F$ we would obtain a path of length at least $(2^{d-1}-1)+1+(2^{d-1}-1)=2^d-1$ which could be extended to an $a-b$ path. Therefore we can choose our $x_E$ for all endblocks $E$ of $G_a$ and $G_b$ such that $x_E\neq p(x_F)$.

We now take our interaction graph $H= \{A,B,\overrightarrow E\} $ to be a bipartite multidigraph whose bipartition consists of the limbs of $a$ and $b$ respectively. Again we additionally adjoin Core$(a)$ and Core$(b)$ to $A$ and $B$ respectively if they are non-empty. Add a directed edge to $H$ for every endblock $E$ in $G_a$ from $K\in A$ to $L\in B$ if $E$ is an endblock of limb $K$ with $x_E\in K$ and $p(x_E)\in L$. Similarly add a directed edge to $H$ for every endblock $F$ in $G_b$ from $L\in B$ to $K\in A$ if $F$ is an endblock of limb $L$ with $x_F\in L$ and $p(x_F)\in K$.  Note again that every limb in $H$ has outdegree at least 1 as it contains an endblock.

We can actually say a lot more about $H$ in the case where one of $a$ or $b$ is not a cutvertex in $G_a$ or $G_b$ - we can guarantee that $p(x_E)\notin \mbox{int}(F)$ for all endblocks $E$ and $F$ of $G_a$ and $G_b$. Indeed, suppose we have $p(x_E)=y\in \mbox{int}(F)$ for some endblocks $E$ of $G_a$ and $F$ of $G_b$ say in limbs $K$ and $L$ respectively. Then by choice of $x_E$ and induction on Theorem \ref{conn} $E$ contains a $\mbox{cutv}(E)-x_E$ path of length at least $2^{d-1}-1$ and $F$ contains a $y-\mbox{cutv}(F)$ path of length $2^{d-1}-2$. This gives a path of length $2^d-2$ from $\mbox{cutv}(E)$ to $\mbox{cutv}(F)$, which extends to a path from $\mbox{Joint}(K)$ to $\mbox{Joint}(L)$. We must have that either $\mbox{Joint}(K)\neq a$ or $\mbox{Joint}(L)\neq b$ since both are not cutvertices. Therefore, extending this path we obtain a path of length at least $2^d-1$ from $a$ to $b$, a contradiction. 

The property that $p(x_E)\notin \mbox{int}(F)$ for all endblocks $E$ and $F$ of $G_a$ and $G_b$ was used crucially throughout the proof of Theorem \ref{connmod}, and knowing it in the case where one of $a$ or $b$ is not a cutvertex actually allows the proofs of Lemma \ref{paths3} and \ref{body} to proceed identically in these cases. The focus therefore will be on obtaining Lemma \ref{paths3} in the case where both $a$ and $b$ are cutvertices of $G_a$ and $G_b$ respectively -- we need not worry about Lemma \ref{body} as it does not apply to this case. While Lemma \ref{paths3} again holds true, a little more work is required than in the original proof in Section 4.




\begin{lem} 
{
\label{path3extension}
$H$ cannot contain an undirected path of length three.
}
\end{lem}

\begin{proof}
{

From the above discussion we need only consider the case in which $a$ and $b$ are cutvertices of $G_a$ and $G_b$ respectively. If one of the interior vertices on this path has two out-neighbours in $Q$ the same argument as in the original proof will create a path between two exit vertices in this limb of length at least $2^d-2$. Extending this path through $Q$ as in Theorem \ref{paths3} gives us an $a-b$ path of length at least $2^d-1$. Similarly, if both endvertices on this path have out-neighbours in $Q$ (that is $\overrightarrow{V_0V_1}$ and $\overleftarrow{V_2V_3}$ are edges of $Q$) we can find a paths of length at least $2^{d-1}-1$ in both $V_0$ and $V_3$, which again can be joined through $Q$ to give an $a-b$ path of length at least $2^d-1$ as required. This just leaves the case of a directed path 
\begin{equation}
{
\label{description}
\overrightarrow{V_0V_1}, \overrightarrow{V_1V_2} \mbox{ and } \overrightarrow{V_2V_3}.
}
\end{equation} While here we obtain a path of length at least $2^{d-1}-1$ from the edge $\overrightarrow{V_0V_1}$ as before, in $V_1,V_2,V_3$ we might not be able to guarantee a full endblock path. Indeed, we may now have the possibility that the edges $\overrightarrow{V_{i-1}V_i}$ and $\overrightarrow{V_iV_{i+1}}$ correspond to one edge entering an endblock $E$ by a vertex $x$ in its interior and the other edge leaving E by a vertex $y$ in its interior. This does not allow us to use induction on Theorem \ref{conn} as $\mbox{cutv}(E)\in E-\{x,y\}$ may have degree lower than $d-1$. 

However, if this does not happen at one of $V_1$ or $V_2$ the same proof applies. 
Also if the exit vertex $x$ of $V_2$ guaranteed by $\overrightarrow{V_{2}V_3}$ had $p(x)$ in the interior of an endblock of $V_3$ we would be able to find our two endblock paths, one in $V_0$ as mentioned already of length at least $2^{d-1}-1$ and the other in $V_3$ of length at least $2^{d-1}-2$. Since joining both of these through $V_1$ and $V_2$ joins at least four more vertices onto these paths, we can extend them to form an $a-b$ path of length at least $2^{d}+1$, more than required. Therefore we must have $p(x)\notin \mbox{int}(E)$. 

But now take any outneighour of $V_3$ in $H$. Combined with our path $Q$ above it is easily seen we can obtain a path $Q'$ of length three which is either (i) not of the form (\ref{description}), or (ii) contains $V_3$ as an interior vertex and allows for a full endblock path to be build through it. In both cases we are done.
}
\end{proof}

The fact that Theorem \ref{path3extension} holds for $G$ again enables us to guarantee that $H$ has at least two connected components. As before Lemma \ref{body} again gives a connected component $C$ of $H$ consisting entirely of limbs. 

Now Theorem \ref{nice} still holds with an identical proof -- the slight variation in the definition of $H$ allows us to guarantee that $|S|,|T|\geq 2$ in the case where $C$ consist of exactly two vertices and that $t'\geq 1$ when it consists of at least three, which ensures 2-connectivity. This time however, it guarantees a path of length at least $2^{d-1}-2$ from any $v\in J-\{a',b'\}$ to $a'$ not containing $b$ or to $b'$ not containing $a$. 
Take $J$ in $G_C$ as guaranteed by Lemma \ref{nice}.







\begin{lem} 
{
\label{noedge}
There does not exist an edge in $G$ from $v\in J-\{a',b'\}$ to $G-J$
}
\end{lem}

\begin{proof}
{
For contradiction suppose $v\in J-\{a',b'\}$ had a neighbour $w$ outside of $J$. Without loss of generality take $v\in G_b$. Then $w\notin G_C$ by Theorem \ref{nice}(i) and so $w\in K$ for some limb $K$ of $a$ say or $w\in \mbox{Core}(a)$. First take $w\in K$, $K\in C'$ for some connected component $C'$ of $H$. 

If $w\notin \mbox{int}(E)$ for some endblock $E$ of $K$ take a $w-x_E$ path $P_2$ in $K$ of length at least $2^{d-1}-1$, where $x_E$ is an exit vertex of $E$, which exists by induction on Theorem \ref{conn}. Combining this with the path $P_1$ given from Lemma \ref{nice}(ii) in $J$ from $a'$ to $v$ of length $2^{d-1}-2$ and the edge $x_Ep(x_E)$ we have a path $P_1vwP_2x_Ep(x_E)$ from $a'$ to $p(x_E)$ of length at least $(2^{d-1}-2)+1+(2^{d-1}-1)+1= 2^d-1$. But this path extends to a path from $a$ to $b$, a contradiction. 

If $w\in \mbox{int}(E)$ for some endblock $E$ of $K$, we would like to combine the $\mbox{Joint}(K)-w$ path guaranteed by induction on $E$ with the $v-b'$ path in $J$ as given by Lemma \ref{nice}(ii) using the edge $wv$. This path extends to an $a-b$ path but may only have length $(2^{d-1}-2)+1+(2^{d-1}-2)=2^d-3$, too little for us. 

Instead, look at an outneighbour of $K$ in $H$. If this is a limb then $C'$ must consist entirely of limbs (by Lemma \ref{body}) and therefore contains a path of the form $\overleftarrow{KW}$ or of the form $KVW$ where $\overleftarrow{VW}$ is an edge of $H$ as all limbs have at least one outneighbour in $H$. This allows us to build a path $P$ from $w$ to $\mbox{Joint}(W)$ of length at least $2^{d-1}+1$ in $C'$. Now combining $P$ with an appropriate path from Lemma \ref{nice}(ii) via the edge $vw$ we obtain a path that extends to an $a-b$ path of length at least $(2^{d-1}-2)+1+(2^{d-1}+1)=2^d$, as required -- take this path to be the $a'-v$ path if $W\in B$ or the $b'-v$ path if $W\in A$.

If the outneighbour of $K$ in $H$ is $\mbox{Core}(b)$, again using Lemma \ref{nice}(ii) we can find a $b'-v$ path in $J$ of length at least $2^{d-1}-2$ which extends through $C'$ to give a $y-b'$ path $P_2$ of length at least $2^{d-1}$, where $y\in \mbox{Body}(b)$. Now $H$ must have a third connected component $C''$ containing a limb of $b$ since $b$ has at least two limbs and only one element of $B$ can lie in a component by Lemma \ref{body}. This component gives an $a-z$ path $P_1$ of length at least $2^{d-1}-2$ where again $z\in \mbox{Body}(b)$ and $P_1$ and $P_2$ are disjoint. As in the proof of Lemma \ref{paths3} we can join $P_1$ and $P_2$ together in $\mbox{Core}(a)$ with a small use of 2-connectivity to give an $a-b$ path of length at least $2^d-1$ as required. This completes the case when $w\in K$.

Finally, the case where $w\in \mbox{Core}(a)$ follows a similar argument. 
}
\end{proof}


Using Lemma \ref{noedge} we can apply Theorem \ref{conn} to $J$ taking $a'$ in place of $a$ and $b'$ in place of $b$. This guarantees a path of length $2^{d}-2$ from $a'$ to $b'$. Moreover, unless $J$ is isomorphic to $Q_d$ with $a=a'$ and $b=b'$ where $a$ and $b$ are at even Hamming distance, $J$ contains a path of length at least $2^{d}-1$ between $a$ and $b$, so we may assume this is the case. Since $G$ is not isomorphic to $Q_d$, the graph $G'=G[V(G)-J\cup \{a,b\}]$ is non-empty and all $v$ in $G'-\{a,b\}$ have degree at least $d$ in $G'$. 

If $a$ and $b$ both have more than two limbs in $G'$, they guarantee that $G'$ is 2-connected. In this case since $|G'|<|G|$ we can apply Theorem \ref{conn} to $G'$. This gives an $a-b$ path in $G'$ of length at least $2^d-1$ unless $G'$ is isomorphic to $Q_d$. If $G'$ was isomorphic to $Q_d$ then $J$ and $G'$ would both contain the subcube containing $a$ and $b$, which contains at least four points since $a$ and $b$ are at even Hamming distance. But from construction $G'$ and $J$ only share $a$ and $b$, so $G'$ is not isomorphic to $Q_d$ and therefore contains an $a-b$ path of length at least $2^d-1$.

If one of $a$ and $b$ has exactly one limb, $a$ say, $G'$ must be of the form $G_C$ for some component $C$ of $H$ (as all limbs of $b$ must have a out-neighbour in $H$). But then we can apply Theorem \ref{nice} to $G'$ to obtain a 2-connected subgraph $\widetilde{J}$ and vertices $\widetilde{a}\in G'_a$ and $\widetilde{b}\in G'_b$. As in Lemma \ref{nice}(i) for any $v\in \widetilde{J}-\{ \widetilde{a},\widetilde{b}\}$, $\widetilde{J}$ contains all neighbours of $v$ in $G_C=G'$. As such $v$ can have no neighbours in $G$ other than those in $G'$ we have $d_{\widetilde{J}}(v)=d_{G}(v) \geq d$. Theorem \ref{conn} now holds for $\widetilde{J}$ taking $\widetilde{a}$ and $\widetilde{b}$ in place of $a$ and $b$ so $\widetilde{J}$ contains a $\widetilde{a}-\widetilde{b}$ path of length at least $2^d-2$ which extends to an $a-b$ path in $G'$ of length at least $2^{d}-2$ in $G$. 
Again as above, since $J$ and $\widetilde{J}$ cannot both be isomorphic to $Q_{d}$ if $a$ and $b$ are at even Hamming distance, $\widetilde{J}$ must contain an $a-b$ path of length at least $2^d-1$, as required.\\




Lastly, we show that the degree condition can again be removed. As in Section 6 we can assume that $d_{G_b}(b)\geq 2$ and that $a$ has a neighbour $v\in G_b$, $v\neq b$ with $v\in E_v$ an endblock of $G_b$ -- the proof of Lemma \ref{remove} is identical. In order for the previous argument to be inapplicable $a$ must have exactly one neighbour $a'$ in $G_a$. Again we switch attention to the limbs of $a'$ and $b$ to construct the interaction digraph $H$. Note that both $a'$ and $b$ have at least 2 limbs.

Now each endblock $F\neq E_v, \{a,a'\}$ of $a'$ or $b$ has at least two exit vertices $x$ and $y$ such that $F$ contains a path of length at least $2^{d-1}-1$ from $\mbox{cutv}(F)$ to $x$ and to $y$. We choose one of these for $x_F$ with the condition that $p(x_F)\notin \{a,a',b\}$, which is possible since $p(a)\in E_v$. Additionally, let $x_{E_v}=v$. Using these vertices construct the interaction digraph $H$ as before.

We claim that again $p(x_E)\notin \mbox{int}(F)$ for all endblocks $E$ and $F$ of $a'$ and $b$, when $F\neq \{a,a'\}$. Otherwise there exists a path $P_1$ from $a'$ to $x_E$ of length at least $2^{d-1}-1$ and a path $P_2$ from $p(x_E)$ to $b$ of length at least $2^{d-1}-2$. But then we have a path $aa'P_1x_Ep(x_E)P_2$ of length at least $1+(2^{d-1}-1)+1+(2^{d-1}-2)=2^d-1$ from $a$ to $b$, a contradiction.

This allows us to again establish Lemma \ref{paths3} and Lemma \ref{body} for $G$ since the problem of entering and leaving an endblock $E$ through vertices in its interior cannot happen. These give a component $C$ of $H$ consisting entirely of limbs of $a'$ and $b$, with $\{a,a'\}\notin C$. Now we can apply Lemma \ref{nice} to $G_C$ to obtain $J$, $a''$, $b''$ as before. 

If no $u\in J-\{a'',b''\}$ has a neighbour outside of $J$ then by induction on Theorem \ref{conn} $J$ contains an $a''-b''$ path $P$ of length at least $2^d-2$. As extending $P$ to an $a-b$ path adds at least one more edge $aa'$, $G$ contains an $a-b$ path of length at least $2^d-1$, a contradiction. Therefore we may assume some $u \in J-\{a'',b''\}$ has a neighbour $w$ outside of $J$. 

Now notice that the proof of Lemma \ref{nice}(ii) actually gives an $a''-u$ path not containing $b$ and a $b''-u$ path not containing $a$ in $J$ of length at least $2^{d-1}$ in this case. Indeed if we are looking for such an $a''-u$ path, as before $J$ contains an endblock $F$ on the opposite side of $J$ to $u$ (that is $F\subset J\cap G_a$ if $u\in G_b$ and $F\subset J\cap G_b$ if $u\in G_a$) for which we can find vertex disjoint paths between $\{a'',u\}$ and $\{\mbox{cutv}(F),y\}$ for some vertex $y\in \mbox{int}(F)$. The path containing $u$ here must have length at least 2 since $p(u)=w$ which lies outside of $J$. Combining these with the $\mbox{cutv}(F)-y$ path of length $2^{d-1}-2$ in $F$ gives the required path.

If $w\in G_{C'}$ with $C'$ a component of $H$ not containing $\{a,a'\}$ then the remainder of the proof is exactly as in the case where $d_{G_a}(a)\geq 2$. So we can assume $\{a,a'\}\in C'$. Clearly $w\neq a$ as $u\neq a',v$. If $w\in \mbox{int}(E_v)$ then $E_v$ contains a $\mbox{cutv}(E_v)-w$ path of length at least $2^{d-1}-2$. Combining this path via the edge $uw$ with the $a''-u$ path of length at least $2^{d-1}$ in $J$ we have an $a''-\mbox{cutv}(E_v)$ path of length at least $2^d-1$ which extends to an $a-b$ path, as required. If $w\notin \mbox{int}(E_v)$ then $G_{C'}$ contains a $w-a$ path $P_1$ of length at least $2^{d-1}-1$ passing through $E_v$. Combining this with the $u-b'$ path $P_2$ in $J$ of length at least $2^{d-1}$ with the edge $uw$ we have an $a-b'$ path $P_1wuP_2$ of length at least $2^d$. As this extends to an $a-b$ path, this finishes the proof of Theorem \ref{conn}. \hspace{11cm} $\square$ 




























\section{Generalizations}

The reader might notice that we have used very little about $Q_n$ in the proof of Theorem \ref{conn}. The $n$-dimensional grid ${\Z}^n$ is the graph whose vertex set consists of $n$-tuples with entries in $\Z$ and in which two vertices $x$ and $y$ are adjacent if $|x_i-y_i|=1$ for some $i\in [n]$ and $x_j=y_j$ for all $j\neq i$. The next theorem extends Theorem \ref{conn} (and therefore Theorems \ref{mainthm} and \ref{cyclethm}) to subgraphs of $\Z^d$.

\begin{thm}
{
Let $G$ be a 2-connected subgraph of ${\Z}^n$ and $a,b\in V(G)$. Suppose that $d(z) \geq d$ for all $z \in V(G)-\lbrace a,b\rbrace$. Then $a$ and $b$ are joined by a path of length at least $2^d-2$. Furthermore unless $G$ is isomorphic to $Q_d$ with $a$ and $b$ at even Hamming distance from each other, $G$ contains an $a-b$ path of length $2^d-1$.
}
\end{thm}

\begin{proof}
{
The crucial property of $\Z ^n$ here is that we can always find a splitting of $G$ into two connected pieces, $G_a$ and $G_b$ with $a\in G_a$ and $b\in G_b$ such that $d_{G_a}(a)\geq 1$ and $d_{G_b}(b)\geq 1$ and all $v\in G$ lose at most one neighbour in their piece. Indeed, taking some coordinate $j$ on which $a$ and $b$ differ, say with $a_j>b_j$, let $G_1$ be the induced subgraph of $G$ consisting all vertices $v$ with $v_j\geq a_j$ and $G_2$ be the induced subgraph of $G$ consisting of all $w$ for which $w_j<a_j$. Again with the same modification to these graphs as in Lemma \ref{splitting} we obtain connected graphs $G_a$ and $G_b$ with the required degree conditions. From here on the proof is identical to that of Theorem \ref{conn}.
}
\end{proof}

Moreover, the same proof also extends to subgraphs of the discrete torus $C_k^{n}$ provided $k\geq 4$. Now we cannot expect a bound of the form $C2^d$ as above for subgraphs of the discrete torus $C_3^{d}$ as this graph has minimum degree $2d$ but only $3^d$ points. This shows that given a subgraph $G$ of $C_3^{n}$ of minimal degree at least $d$ we cannot in general guarantee a path of length more than $3^{\frac{d}{2}}-1$ in $G$. 

Why does our approach not work in this case? The main reason is that we cannot guarantee a partition into two subgraphs such that all vertices lose at most one neighbour in their piece. Can we still guarantee an exponentially long path in this case? 

The following general result shows that we can. 

\begin{thm}
{
\label{gen} Let $k\in \N$ and $G$ be a 2-connected graph with $a,b\in V(G)$. Suppose $d(v)\geq d$ for all $v\in V(G)-\{a,b\}$. Furthermore, suppose that $G$ has the following property:
\begin{quotation}
{\noindent Given any two vertices $x,y\in G$, there is a partition of $V(G)$ into two sets $X$ and $Y$ 
with $x\in X$ and $y\in Y$ such that $d_{G[X]}(v)\geq d(v)-k$ for all $v\in X$ and $d_{G[Y]}(v)\geq d(v)-k$ for all $v\in Y$.}
\end{quotation}
Then $G$ contains an $a-b$ path of length at least $2^{\frac{d}{k+2}}$.
}
\end{thm}

Note that if the property above holds for $G$, it also holds for all subgraphs of $G$. As an immediate corollary of Theorem \ref{gen} we 
have the following:

\begin{cor}
 {
 Every subgraph of $C_3^n$ of minimum degree at least $d$ contains a path of length at least $2^{\frac{d}{4}}$.
 }
\end{cor}

It would be interesting to decided what the correct lower bounds for the length of the longest path in subgraphs of $C_3^n$ with minimum degree at least $d$.

\begin{conjecture}
 {
 Given a subgraph $G$ of $C_3^n$ with minimum degree at least $d$, $G$ must contain a path of length at least $3^{\frac{d}{2}}-1$.
 }
\end{conjecture}

Another consequence of Theorem \ref{gen} is the following result for product graphs.

\begin{thm}
{
Let $G_1,\ldots ,G_l$ be graphs with maximum degree at most $k$. Then given any subgraph $G$ of the Cartesian product graph $\prod_{i=1}^{l}G_i$  of minimum degree at least $d$, $G$ contains a path of length at least $2^{\frac{d}{k+2}}$.
}
\end{thm}

The proof of Theorem \ref{gen} is similar to that of Theorem \ref{conn} but shorter.

\begin{proof}
{
The proof is again by induction on $d$. It suffices to prove the result for $d\geq k+4$ as otherwise it follows from 2-connectivity. As in the proof of Theorem \ref{conn} we wish to split $G$ into two subgraphs $G_a$ and $G_b$ with $a\in G_a$ and $b\in G_b$, which is the motivation for the above splitting property. However, simply taking $a$ and $b$ in place of $x$ and $y$ might not be useful as both $a$ and $b$ can have degree as low as two in $G$ in which case in the partition guaranteed above $a$ may end up with all its neighbours in $Y$. 
Instead we pick a neighbour $a'\neq b$ of $a$ and a neighbour $b'\neq a$ of $b$. The fact that $G$ is 2-connected ensures it is possible to pick $a'\neq b'$. Now take the partition guaranteed from our splitting property above with $x=a'$ and $y=b'$. Moving $a$ to $X$ and $b$ to $Y$ as needed we have that $d_{G[X]}(v)\geq d(v)-k-1$ for all $v\in X-a$ and similarly for $v\in Y-b$. Both $a$ and $b$ now have at least 1 neighbour in $G[X]$ and $G[Y]$ respectively. Finally, denoting the connected component of $G[X]$ containing $a$ by $C_a$, let $G_b$ be the connected component of $G-C_a$ containing $b$ and $G_a=G[V(G)-V(G_b)]$. Note that $G_a$ and $G_b$ are connected with $a\in G_a$, $b\in G_b$. Moreover, $d_{G_a}(v)\geq d(v)-k-1$ for all $v\in G_a-a$ and $d_{G_b}(v)\geq d(v)-k-1$  for $v\in G_b-b$.

We will again analyse the block-cutvertex decompositions of $G_a$ and $G_b$. The following lemma will be very useful below.

\begin{lem}
{
\label{endblock}
Let $E$ be an endblock of $G_a$ or $G_b$ with $a,b\notin \mbox{int}(E)$. Then given any two vertices $u,v\in \mbox{int}(E)$, $G[E]$ contains a path of length at least $2^{\frac{d-k-2}{k+2}}$ from $u$ to $v$.
}
\end{lem}

\begin{figure}
\centering
\input{smallerlongpath.pstex_t}
\caption{Cases where $G'$ is not 2-connected in Lemma \ref{endblock}}
\label{smallerlongpath}
\end{figure}

\begin{proof}
{
Look at the block-cutvertex decomposition of $G'=G[E]-\mbox{cutv}(E)$. Since $E$ is 2-connected (as $d\geq k+4$), $G'$ is connected and $\mbox{cutv}(E)$ must have a neighbour in the interior of every endblock of $G'$. Note that every vertex $v\in G'$ has $d_{G'}(v) \geq d_G(v)-k-2$. In particular, since $d\geq k+4$ each endblock $F$ of $G'$ is 2-connected and has at least three vertices so that we can by induction apply Theorem \ref{gen} to it. If $G'$ is 2-connected then by induction on Theorem \ref{gen} $G'$ contains the desired path from $u$ to $v$. Thus we may assume that $G'$ is not 2-connected. If $u\in \mbox{int}(F_1)$ and $v\in \mbox{int}(F_2)$ where $F_1$ and $F_2$ are two distinct endblocks of $G'$ then by induction on Theorem \ref{gen}, $G[F_1]$ and $G[F_2]$ contain $u-\mbox{cutv}(F_1)$ and $\mbox{cutv}(F_2)-v$ paths respectively, each of length at least $2^{\frac{d-k-2}{k+2}}$. Joining $\mbox{cutv}(F_1)$ to $\mbox{cutv}(F_2)$ by a third path in $G'$ and combining all three of these paths, we get a $u-v$ path of length at least $2^{\frac{d}{k+2}}$, as required. Therefore since $G'$ contains at least two endblocks, we can assume that one of these, say $F$, does not contain $u$ or $v$ in its interior. Contracting $\mbox{int}(F)$ down to a single vertex in $G[E]$, the resulting graph is still 2-connected. Therefore, as in the proof of Lemma \ref{nice}, $G[E]$ contains two vertex disjoint paths $P_1$ and $P_2$ from the set $\{u,v\}$ to $\{\mbox{cutv}(F),w\}$ for some $w\in \mbox{int}(F)$, with $(P_1\cup P_2)\cap (F-\{\mbox{cutv}(F),w\})=\emptyset$. Now using induction on Theorem \ref{gen} in $F$, it contains a path $P_3$ of length $2^{\frac{d-k-2}{k+2}}$ from $\mbox{cutv}(F)$ to $w$. Piecing $P_1$, $P_2$ and $P_3$ together we obtain our desired path.
}
\end{proof}





Again we have:

\begin{prop}
{
\label{intnew}
Let $E$ be an endblock of $G_a$ not containing $a$ and $F$ an endblock of $G_b$ not containing $b$. Then $G$ does not contain an edge from $\mbox{int}(E)$ to $\mbox{int}(F)$
}
\end{prop}

\begin{proof}
{
Exactly as in Proposition \ref{int}.
}
\end{proof}


\begin{lem}
{
\label{newlist}
We have the following:
\begin{itemize}
{
\item[\emph{(i)}] Given any endblock $E$ of $G_a$ not containing $a$, there are two disjoint edges from $\mbox{int}(E)$ to $G_b$ in $G$.

\item[\emph{(ii)}] $G_a$ contains an endblock not containing $a$.
}
\end{itemize}
}
\end{lem}



\begin{proof}
{
(i) $E$ must have an exit vertex $x_1$, with neighbour $y\in G_b$, as $G$ is 2-connected. If it had only one, $G'=G[E]$ is 2-connected and every $v\in G'-\{x_1,\mbox{cutv}(E)\}$ has degree at least $d$. Therefore, by induction on Theorem \ref{gen}, $G'$ contains a path of length at least $2^{\frac{d}{k+2}}$ from $x_1$ to $\mbox{cutv}(E)$. Extending this path from $\mbox{cutv}(E)$ to $a$ in $G_a$ and from $y$ to $b$ in $G_b$ we obtain an $a-b$ path of desired length. Therefore we may assume $E$ contains a second exit vertex $x_2$. Now if the vertices in ${\mbox{int}(E)}$ were only adjacent to $y$ in $G_b$, $x_1y$ and $x_2y$ must be edges of $G$. Then $G''=G[E\cup \{y\}]$ is 2-connected and $d_{G''}(v)\geq d$ for every $v\in G''-\{y,\mbox{cutv}(E)\}$. By Theorem \ref{gen} $G''$ contains a $\mbox{cutv}(E)-y$ path of length at least $2^{\frac{d}{k+2}}$. Again, extending this to a path from $a$ to $b$, we have an $a-b$ path of length at least $2^{\frac{d}{k+2}}$. Therefore we may assume the two edges exist or we are done.

(ii) The proof is almost identical to the proof of Lemma \ref{list}(ii).
}
\end{proof}

Take an endblock $E$ of $G_a$ not containing $a$, as guaranteed by Lemma \ref{newlist}(ii). We can choose $E$ such that $a$ and all $v\in G_a-E$ not contained in the interior of an endblock of $G_a$ lie in the same connected component of $G_a-E$ (e.g. pick a block $B$ in $G_a$ containing $a$ and choose $E$ to be a block at maximum distance from $B$ in $\mathcal{B}(G_a)$). Let $x_1y_1$ and $x_2y_2$ be the disjoint edges of $G$ with $x_1,x_2\in \mbox{int}(E)$ and $y_1,y_2\in G_b$ guaranteed by Lemma \ref{newlist}(i). By Proposition \ref{intnew}, $y_1,y_2\notin \mbox{int}(F)$ for all endblocks $F$ of $G_b$ not containing $b$ in its interior. 

\begin{figure}
\centering
\input{Generalized.pstex_t}
\caption{Path created in Theorem \ref{gen}}
\label{Generalized}
\end{figure}

Now looking at the block-cutvertex decomposition of $G_b$ we can choose two vertex disjoint paths in $G_b$ from $\{y_1,y_2\}$ to $\{b, \mbox{cutv}(F)\}$ where $F$ is some endblock of $G_b$ not containing $b$. Lets say that these paths are $P_3$ from $\mbox{cutv}(F)$ to $y_1$ and $P_5$ from $y_2$ to $b$. Applying Lemma \ref{newlist}(i) to $F$ we see that there exists $u\in \mbox{int}(F)$ adjacent to some $v\in G_a$, $v\neq \mbox{cutv}(E)$. Furthermore, by Proposition \ref{intnew} $v\notin \mbox{int}(E')$ for any endblock $E'$ of $G_a$. From our choice of $E$ there exists an $a-v$ path $P_1$ in $G_a-E$. Finally by induction on Theorem \ref{gen}, $F$ contains a $u-\mbox{cutv}(F)$ path $P_2$ of length at least $2^{\frac{d-k-1}{k+2}}$ and by Lemma \ref{endblock} $E$ contains an $x_1x_2$ path $P_4$ of length at least $2^{\frac{d-k-2}{k+2}}$. Combining these five paths we obtain an $a-b$ path $P=P_1vuP_2P_3y_1x_1P_4x_2y_2P_5$ of length at least $2^{\frac{d-k-1}{k+2}}+2^{\frac{d-k-2}{k+2}}>2^{\frac{d}{k+2}}$ as required. 
}
\end{proof}

The cycle analogues of the above theorems can be obtained in a similar fashion to the proof of Theorem \ref{cyclethm} from Theorem \ref{conn}.

As mentioned in the Introduction, we do not know the correct bound for the length of the longest path in a subgraph of $Q_n$ when the minimum degree condition in Theorem \ref{mainthm} is replaced by an average degree condition. Is the following possible?
\vspace{0.25cm}

\begin{conjecture} 
 {
Every subgraph of $Q_n$ with average degree at least $d$ contains a path of length at least $2^d-1$.
 }
\end{conjecture}















\section*{Acknowledgements}
{
I would like to thank my supervisor Imre Leader for many helpful conversations and David Conlon for reading through an earlier version of this paper.
}



















2010-06-16T02:01:53.000
1006
1006.3049
en
https://arxiv.org/abs/1006.3049
Let $Q_n$ denote the graph of the $n$-dimensional cube with vertex set $\{0,1\}^n$ in which two vertices are adjacent if they differ in exactly one coordinate. Suppose $G$ is a subgraph of $Q_n$ with average degree at least $d$. How long a path can we guarantee to find in $G$?Our aim in this paper is to show that $G$ must contain an exponentially long path. In fact, we show that if $G$ has minimum degree at least $d$ then $G$ must contain a path of length $2^d-1$. Note that this bound is tight, as shown by a $d$-dimensional subcube of $Q_n$. We also obtain the slightly stronger result that $G$ must contain a cycle of length at least $2^d$ and prove analogous results for other `product-type' graphs.
Combinatorics (math.CO)
Long paths and cycles in subgraphs of the cube
Qwen/Qwen-72B
1. YES
2. YES