2

I'm working on problem #18 of section 11.3 from Ralph P. Grimaldi's textbook Discrete and Combinatorial Mathematics an Applied Introduction, fifth edition.

  1. Let $k$ be a fixed positive integer and let $G=(V,E)$ be a loop-free undirected graph, where $deg(v) \geq k$ for all $v \in V$. Prove that $G$ contains a path of length $k.$

I'm really having trouble understanding how to tackle the problem because the number of vertices is not given. At the end of section 11.1 states that when a graph is a multigraph it will be stated, however it is not stated in this problem that G cannot be a multigraph.

If G can be a multigraph then clearly the statement is false:

Start with $K_n$ the complete graph on $n$ vertices $v_1,v_2,...,v_n$ then add the edges $\{v_1,v_2\}$,$\{v_2,v_3\},...,\{v_{n-1},v_n\},\{v_n,v_1\}$, then every vertex has degree $n-1+2=n+1$, however there are only $n$ vertices, thus there is no path of length $n+1$.

For example with $K_5$ (the added edges being $\color{red}{red}$):

enter image description here

How do I go about working this problem?

no lemon no melon
  • 2,129

2 Answers2

1

Let $G$ have no self-loops and parallel edges. Then $G$ has atleast $k+1$ vertices. Start with any vertex $v_1\in V$. It has $k$ distinct neighbours, chose any one neighbour, say $v_2$. Now $v_2$ has $k$ distinct neighbours but one of them is $v_1$, which can't be selected as the next vertex of the path since we can't repeat vertices. Select $v_3\ne v_1$ neighbour of $v_2$. You can proceed in a similar fashion till $v_{k+1}$ since at $v_{k+1}$ it is possible that the $k$ neighbours of $v_{k+1}$ are the previously selected $k$ vertices of the path. The length of the path constructed is $k$.

Note that this theorem does not hold when $G$ has parallel edges or self-loops. Consider a graph of two vertices with two parallel edges between them, then $\deg(v)\ge2$ but you can't have a path of length $2$. Alternatively, to a graph of a single vertex, you can keep adding self-loops to make the degree of the vertex larger but you don't have any path of length $\ge1$ in the graph. Self-loops and parallel edges create trouble because for a vertex of degree $m$ you cannot assume $m$ distinct neighbours.

Shubham Johri
  • 17,659
0

Welcome to MSE!

Hint:

This is an example of a "greedy algorithm". The idea is to just keep adding vertices into your path while avoiding "obvious" problems. In this case, you never want to repeat a vertex. In slightly more detail:

Pick a vertex $v_1$. It has degree at least $k$, so it has at least $k$ neighbors. Pick a neighbor $v_2$.

Now this vertex has degree at least $k$, but there's one vertex we don't want to go back to ($v_1$). Thankfully $k>1$, so we can pick a new vertex $v_3$.

But this new vertex has degree $k$ too. Of course, now there are two vertices which we want to avoid ($v_1$ and $v_2$). Thankfully $k > 2$, and we can pick a new vertex $v_4$.

Keep doing this until you can no longer guarantee a new vertex exists. How long must your path be? Can you make this argument precise?

I hope this helps ^_^

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87