# Is there a known extension of Dirac's / Ghoulia-Houri's theorems for $k$-path existence?

In the well studied problem of Hamiltonicity, several papers/theorems gave sufficient "degree conditions" for the existence of Hamiltonian path in a graph.

These include:

1. Dirac's theorem , 1952, which states that "A simple (undirected) graph with $n$ vertices ($n \geq 3$) is Hamiltonian if every vertex has degree $\frac{n}{2}$ or greater".

2. Ghouila-Houiri 's theorem, ("Une condition suffisante d’existence d'un circuit hamiltonien",1960), which generalized Dirac's result to directed graphs, showing that if $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$ then G is Hamiltonian, where $\delta^+(G)$ is the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree.

3. A theorem from Bang-Jensen and Gutin's book gave a stronger result, which imply that if $\forall v\in V: d_{in}(v)+d_{out}(v)\geq n$ then the graph is Hamiltonian.

The $k$-path problem is a simple generalization of Hamiltonicity asking whether a simple path on $k$ nodes exist in a graph.

What would be the weakest sufficient "degree conditions" from a graph such that it is bound to contain a $k$-path?

• Are you looking for conditions independent to $n$? e.g $\delta^++\delta^- > f(k)$. (I think something like Ramsey theorem works here, sure I don't know any references right now). – Saeed Aug 5 '14 at 21:00
• @Saeed - this is exactly what I'm looking for (although $f(n,k)$ would work too), thanks. – R B Aug 5 '14 at 21:36
• It doesn't work to lower-bound only the sum of the indegree and outdegree. Consider a complete bipartite graph $K_{n,n}$ oriented from one side of the bipartition to the other. The sum of indegree and outdegree is $n$ but the longest directed path has only two nodes. – David Eppstein Aug 5 '14 at 23:02
• @DavidEppstein - thanks for the example. It doesn't have to be the sum of degrees, as in theorems 1,2 in the question if we can get a bound which means $d_{in},d_{out}\geq f(n,k)$ it would be interesting too. Also, it seems to me that $d_{in} + d_{out}\geq \frac{n}{2} + g(k)$ might work. – R B Aug 6 '14 at 6:35
• Maybe $\delta^+ + \delta^-$ together with strongly connectivity condition works. e.g right now David Eppstein's counterexample works because the graph is actually weakly connected. – Saeed Aug 6 '14 at 8:16

I don't know about the weakest possible conditions, but if a graph has a subgraph with minimum degree $k-1$ (that is, if its degeneracy is at least $k-1$) then a greedy algorithm can easily find a path of $k$ nodes starting at any node. The example of $K_{k-1}$, which has no $k$-path and has minimum degree $k-2$, shows that this is tight.
• If the minimum outdegree is at least $k-1$ then the same idea works. (Or, by working backwards, indegree instead of outdegree works too.) As in the undirected case you can find a subgraph maximizing the minimum outdegree by peeling away minimum-outdegree vertices greedily. – David Eppstein Aug 5 '14 at 23:00
• Right, then by your example the best bound till now (that we have in this answer) is $(\delta^-)\delta^+ > k-2$ and seems it's not possible to obtain something like $\delta^+ + \delta^-$ for directed case, except adding additional dependency (as R B mentioned n/2 + g(k) may works). – Saeed Aug 6 '14 at 8:10