4
$\begingroup$

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!

  • 1
    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$.2011-07-17

1 Answers 1

2

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$.

  • 0
    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.2011-07-18