Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm going through a set of notes on Graph Theory. The following theorem is proved:

Theorem 1: Let $G$ be a graph of order $n$ ($ n \geq 3$) such that $ \delta(G) \geq \frac{n}{2} $. Then $G$ is Hamiltonian.

I'm happy with the statement and proof of this theorem. The notes then prove the following theorem:

Theorem 2: Let $G$ be a graph of order $n$ ($n \geq 3$) such that $G$ is connected and $ \delta(G) \geq \frac{k}{2} $, where $ k < n $. Then $G$ has a path of length k.

I'm happy with the proof of this. The notes then make the following remark

Remark: We do need $k < n $, e.g. $ G = K_k $, and we do need $G$ to be connected e.g. two disjoint copies of $K_k$.

I don't understand this remark. Clearly $k$ can't be bigger than $n$ (as there obviously can't be a path through more than $n$ vertices on a graph with $n$ vertices). So the remark must mean we can't have $k = n $. But if $k = n$, then isn't this just the same as Theorem 1? I don't see how the example relates, either; if $ G = K_n $, then the theorem still works?

Thanks for your help!

share|cite|improve this question
Maybe the difference is path vs cycle in conjunction with definition of length? If length=number of edges, Hamiltonian cycle can be made into path of length (n-1) by removing an edge, but of course there will be no path of length n. – Max Jul 17 '11 at 15:44
A guess: The author is showing why each of the requirements in the statement of Theorem 2 is necessary. I agree that a `Remark' usually refers to something non-obvious. – Ben Derrett Jul 17 '11 at 15:50
I'm still unsure why '$k < n$' is necessary. Why couldn't we have $k \leq n $? – Anon Jul 17 '11 at 15:54
I guess it comes down to: is a cycle a path? – Anon Jul 17 '11 at 16:04
You could argue that any graph with at least one edge has paths of unbounded length: just go backwards and forwards on a single edge, as many times as you need. But this lax definition of path is obviously not what is meant in the statement of Theorem 2, so presumably a simple path of length $k$ is what is meant. And a cycle is not a simple path, so a simple path can have length at most $n-1$. – TonyK Jul 17 '11 at 17:12
up vote 2 down vote accepted

Different authors define path differently, but it appears that the author of your notes uses definitions similar to those used in West’s Introduction to Graph Theory. For him a path is ‘a simple graph whose vertices can be ordered so that two vertices are adjacent if and only if they are consecutive in the list’, and a cycle is ‘a graph with an equal number of vertices and edges whose vertices can be placed around a circle so that two vertices are adjacent if and only if they appear consecutively along the circle’. By these definitions a path can never be a cycle: in any listing of the vertices of a cycle in which consecutive vertices in the list are adjacent to each other in the graph, the first and last vertices in the list are also adjacent in the graph. This definition of path also implies that no path in a graph can have more vertices than the graph itself. In particular, $K_n$ contains no path with $n+1$ vertices and hence no path of length $n$.

share|cite|improve this answer
But the problem arises when $k$ is equal to $n$. Then a path can certainly have $n$ distinct vertices! But its length is only $n-1$. – TonyK Jul 17 '11 at 21:11
Yes, the last sentence of the original answer was a bit of a non sequitur, though the correct point was made in the previous sentence. I no longer recall why I wrote it, but I’ve replaced it with one that makes the real point explicitly. – Brian M. Scott Jul 18 '11 at 9:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.