# Thread: Interesting Graph Theory Proof

1. ## Interesting Graph Theory Proof

Hey guys,

I don't want the answer to this I just want some help being able to explain this. I have just started doing graph theory in class, and haven't really figured out how to do the proofs yet. This problem just makes complete sense to me so its one of those that is hard to explain in a "proofy" way for me. Thanks for anyone's help in advance. The question is:

Let $\displaystyle G=(V,E)$ be a graph in which every vertex has degree at least $\displaystyle k\ge 1$. Show that there is a path of length at least k in G.

2. Originally Posted by SaxyTimmy
Let $\displaystyle G=(V,E)$ be a graph in which every vertex has degree at least $\displaystyle k\ge 1$. Show that there is a path of length at least k in G.
Assume that the graph is a simple graph. A path is an alternating sequence of vertices and edges in which on vertex is repeated. (Now in Graph Theory definitions will vary, but this argument should work.)

We can assume that each vertex is of degree $\displaystyle K$ where $\displaystyle K \ge 1$.
The key concept is that there must be at least $\displaystyle K+1$ vertices in the graph.
Start at any vertex. There are $\displaystyle K$ vertices adjacent to that vertex.
Choose a second vertex adjacent to the first. Now there are $\displaystyle K-1$ vertices, other than the first, adjacent to the second vertex.

Do you see how finish?

3. No.... I guess I don't see how to finish. This sucks I thought I completely understood graph theory last week and now this LOL.... oh well if you have extra tips it would be great if not. I will just put a bunch more thought into it.

Edit: Also, I am not sure why there would have to be K + 1 edges for this. Isn't it possible to have more than one edge connecting two vertices? or is this a rule of graphs? I am really not sure we haven't discussed this in class.

4. You may keep on moving to adjacent vertices until there are 0 vertices adjacent to the current vertex untravelled. This gives you a path of length k? Adding more edges will not reduce the length of the path, so there is a path of length at least k?

5. Originally Posted by SaxyTimmy
Also, I am not sure why there would have to be K + 1 edges for this. Isn't it possible to have more than one edge connecting two vertices? or is this a rule of graphs? I am really not sure we haven't discussed this in class.
Did not say that there are K+1 edges, in fact there are more edges.
This is true: there must be at least $\displaystyle K+1$ vertices in the graph.
To finish. Choose a third vertex adjacent to the second but not the first, there at least $\displaystyle K-2$ to choose.
By this inductive process we can sequence of $\displaystyle K+1$ vertices in a path.
That means the path is length $\displaystyle K$.

Now, I did say that this was for a simple graph, no multiple edges.
Depending upon the definition of path, using the one I gave above there is a simple counter-example using a two-vertex multi-graph.

How does your text define a path?

6. Hey,

Sorry I had meant vertices not edges.
For us a path has been defined as: A sequence of distinct vertices v0, v1, v2, ..., vk where each pair of successive vertices {vi, vi+1} form an edge, where i=0...k-1.

Sorry, that I cant use latex for it, but I think that it should be self explanatory (numbers to the right of letters are generally subscripts).

7. If a vertex is of degree 2 then there must two distinct vertices (in a simple graph) adjacent to it. That makes 3 vertices. If each vertex has degree at least K then there must be at least K+1 vertices.

Again, there is a counter example to this statement if you use multi-graphs.