Theorem: A graph with $n^2+1$ vertices has a path of length $n$ Theorem:
G is a graph with $n^2+1$ vertices. There is a path of length $n$ either in G or in the complement graph of G.
How would you show this? Is there a more general theorem one must use?
 A: *

*For any vertex $v \in V(G_{n^2+1})$,
$deg_{G_{n^2+1}}(v)=d \Leftrightarrow deg_{\bar{G}_{n^2+1}}(v)=n^2-d$, since $G_n \cup\bar{G_n}=K_{n^2+1}$ and $deg_{G_{n^2+1}}(v) + deg_{\bar{G}_{n^2+1}}(v)=n^2$.
Obviously $d \in \{0,1,2,\ldots,n^2\}$.


*Now, we shall use the above result along with the theorem that if the minimum degree of a vertex in a graph $G$ is $\delta$, then $G$ has a path of length $\delta$, with the following proof:
Let's consider one of the longest paths in $G$, namely $P=(v_0,v_1,\ldots, v_k)$, the length of the path is $k \geq 0$, with equality holding when we have $v_0=v_k$.
Let's consider the end vertex $v_k$ from the path, obviously $deg(v_k)\geq \delta$.
Also, let's convince ourselves that all the neighbors of $v_k$ must be on $P$, since if some neighbor $u$ was not on $P$, then we can always connect $v_k$ with $u$ and consider the path $P \cup {u}$, thereby increasing the length of the longest path $P$, a contradiction.
Which means all of $deg(v_k) \geq \delta$ neighbors of $v_k$ must be present as vertices on the path $P \implies$ length of path $P$ is at least $\delta$.


*Let's say $v$ is the minimum-degree vertex in $G_{n^2+1}$.
If $deg_{G_{n^2+1}}(v)=d \geq n$, then $G_{n^2+1}$ contains a path of length $n$ by the above theorem, we are done.
Otherwise, if $deg_{G_{n^2+1}}(v)=d < n \implies deg_{\bar{G}_{n^2+1}}(v)=n^2-d > n^2-n \geq n$, for $n \geq 2$ and then $\bar{G}_{n^2+1}$ contains a path of length $n$ by the above theorem.
Only trivial case that is left out is $n=1$, for which $G$ has $n^2+1=2$ vertices and obviously there will be an edge (i.e., a path of length $n=1$) in between them in either $G$ or $\bar{G}$, which competes the proof.
A: Here is an argument based on induction that doesn't use degrees.
Claim: In any graph G with $\ge n^2+1$ vertices, there is a path of length $n$ either in G or in the complement graph of G.
Proof by induction on $n$. In the base case, $n=0$, there is at least one vertex, and there is a trivial path of length 0.
In the inductive case, since the graph has $n^2+1 = (n-1)^2 + 2(n-1) + 1 + 1 \ge (n-1)^2 + 1$ vertices, there is a path of length $n-1$ in either the graph or the complement. Removing these $n-1$ vertices, we have $(n-1)^2 + (n-1) + 1 + 1 \ge (n-1)^2 + 1$ remaining, and there is another path (in the graph or the complement) in the remaining vertices. Doing this a third time, we get a third path.
Of these three paths, assume WLOG that two are paths of the graph itself, rather than the complement. If there is an edge between a node in the first path and a node in the second, then by taking this edge and longer parts of the two preexisting paths starting at this edge, we can make a path of length at least $(n-1)/2 + (n-1)/2 + 1 = n$. If there are no edges between these paths, we can create a path in the complement of length $2n$.
A: If $G=(V,E)$ is a graph of order $mn+1$, then either $G$ contains a path of length $n$, or else the complementary graph $\overline G$ contains a complete graph $K_{m+1}$. (I.e., the Ramsey number $R(P_{n+1},K_{m+1})\le mn+1$; in fact it's easy to see that equality holds.)
Proof. Let $H_1$ be a maximal path in $G$; thus the endvertices of $H_1$ have no neighbors in $V\setminus V(H_1)$. Having defined $H_1,\dots,H_k$, if $V\setminus(V(H_1)\cup\cdots\cup V(H_k))\ne\varnothing$, let $H_{k+1}$ be a maximal path in $G-(V(H_1)\cup\cdots\cup V(H_k))$.
If we assume that $G$ has no path of length $n$, then each path $H_i$ has at most $n$ vertices. Since $G$ has $mn+1$ vertices, we have defined at least $m+1$ vertex-disjoint paths $H_1,\dots,H_{m+1}$. Let $v_i$ be an endvertex of the path $H_i$. If $1\le i\lt j\le m+1$ then $v_i$ is not adjacent to $v_j$; if it were then $H_i$ would not have been maximal. Thus $\{v_1,\dots,v_{m+1}\}$ is an independent set in $G$ and a clique in $\overline G$. Q.E.D.
On the other hand $mK_n$, the union of $m$ disjoint copies of $K_n$, is a graph of order $mn$ which contains no path of length $n$ and whose complement contains no $K_{m+1}$. Thus the Ramsey number $R(P_{n+1},K_{m+1})$ is equal to $ mn+1$.
If you just want monochromatic paths, then $R(P_m,P_n)=n+\lceil m/2\rceil-1$ for $n\ge m\ge2$; see L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 10 (1967), 167-170 (pdf).
