<p>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 <a href="https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)" rel="nofollow">degeneracy</a> 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.</p>

CC BY-SA 3.0
2014-08-05T21:09:32.677Z
OP's examples are more toward directed graphs, I don't know if OP also interested in undirected case (well seems we can relax your condition to get result for a directed graph but directed case is not trivial, at least for me).
Saeed
CC BY-SA 3.0
2014-08-05T23:00:38.623Z
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
CC BY-SA 3.0
2014-08-06T08:10:21.170Z
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
CC BY-SA 3.0
2014-08-05T21:02:38.627Z
2014-08-05T21:02:38.627Z
David Eppstein
<p>In the well studied problem of Hamiltonicity, several papers/theorems gave sufficient "degree conditions" for the existence of Hamiltonian path in a graph.</p>

<p>These include:</p>

<ol>
<li><p><a href="http://en.wikipedia.org/wiki/Dirac%27s_theorem_on_Hamiltonian_cycles#Bondy.E2.80.93Chv.C3.A1tal_theorem" rel="nofollow">Dirac's theorem</a> , 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".</p></li>
<li><p>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.</p></li>
<li><p>A theorem from <a href="http://www.springer.com/new+&amp;+forthcoming+titles+%28default%29/book/978-1-84800-997-4" rel="nofollow">Bang-Jensen and Gutin's book</a> 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.</p></li>
</ol>

<hr>

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

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

CC BY-SA 3.0
2014-08-05T21:00:24.087Z
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
CC BY-SA 3.0
2014-08-05T21:36:52.977Z
@Saeed - this is exactly what I'm looking for (although $f(n,k)$ would work too), thanks.
R B
CC BY-SA 3.0
2014-08-05T23:02:58.890Z
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
CC BY-SA 3.0
2014-08-06T06:35:43.140Z
@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
CC BY-SA 3.0
2014-08-06T08:16:34.480Z
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
CC BY-SA 3.0
2014-08-06T08:37:28.650Z
@Saeed - what do you mean by it being a counterexample?
It shows that $\delta^+ + \delta^- \geq g(k)$ is not enough, but it still is interesting for $f(n,k)$, or perhaps $\frac{n}{2}+g(k)$.
R B
CC BY-SA 3.0
2014-08-06T08:42:24.930Z
Yes I mean a counter example for $\delta^+ + \delta^- > f(k)$, but still your suggestion seems to be reasonable. But if we want to keep $\delta^+ + \delta^- > f(k)$, then simply adding condition of strongly connectivity (which is very natural) seems resolves many possible counters for $\delta^+ + \delta^- > f(k)$.
Saeed
CC BY-SA 3.0
2014-08-07T10:25:47.970Z
If we consider just $d_{in}+d_{out}$ and adding strongly connectivity, it doesn't work, just consider a complete bipartite graph directed from A->B, add vertices source and terminal then connect source to all others and all others to terminal, finally connect terminal to the source. But if we consider $\delta^+=\min\{v\in V(D)\mid d_{out}(v)\}$ and $\delta^-$ respectively, then seems we don't need any extra condition or dependence to $n$ and graph (subgraph) of $\delta^++\delta^- > f(k)$ has that path.
Saeed
<graph-theory><hamiltonian-paths>
Is there a known extension of Dirac's / Ghoulia-Houri's theorems for $k$-path existence?
R B
# Is there a known extension of Dirac's / Ghoulia-Houri's theorems for $k$-path existence?

(Asked by: username_0 on 2014-08-05)

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](http://en.wikipedia.org/wiki/Dirac%27s_theorem_on_Hamiltonian_cycles#Bondy.E2.80.93Chv.C3.A1tal_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](http://www.springer.com/new+&+forthcoming+titles+%28default%29/book/978-1-84800-997-4) 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?**

**Tags:** graph-theory, hamiltonian-paths

> **Comments:**
> **username_1**: 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).  
> **username_0**: @username_1 - this is exactly what I'm looking for (although $f(n,k)$ would work too), thanks.  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_1**: Maybe $\delta^+ + \delta^-$ together with strongly connectivity condition works. e.g right now username_2's counterexample works because the graph is actually weakly connected.  
> **username_0**: @username_1 - what do you mean by it being a counterexample? It shows that $\delta^+ + \delta^- \geq g(k)$ is not enough, but it still is interesting for $f(n,k)$, or perhaps $\frac{n}{2}+g(k)$.  
> **username_1**: Yes I mean a counter example for $\delta^+ + \delta^- > f(k)$, but still your suggestion seems to be reasonable. But if we want to keep $\delta^+ + \delta^- > f(k)$, then simply adding condition of strongly connectivity (which is very natural) seems resolves many possible counters for $\delta^+ + \delta^- > f(k)$.  
> **username_1**: If we consider just $d_{in}+d_{out}$ and adding strongly connectivity, it doesn't work, just consider a complete bipartite graph directed from A->B, add vertices source and terminal then connect source to all others and all others to terminal, finally connect terminal to the source. But if we consider $\delta^+=\min\{v\in V(D)\mid d_{out}(v)\}$ and $\delta^-$ respectively, then seems we don't need any extra condition or dependence to $n$ and graph (subgraph) of $\delta^++\delta^- > f(k)$ has that path.  

---

## 1 answers

### Answer by username_2 on 2014-08-05. Score: 1

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](https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)) 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.

> **Comments:**
> **username_1**: OP's examples are more toward directed graphs, I don't know if OP also interested in undirected case (well seems we can relax your condition to get result for a directed graph but directed case is not trivial, at least for me).  
> **username_2**: 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.  
> **username_1**: 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 username_0 mentioned n/2 + g(k) may works).  

---

