Let $k\in \mathbb{Z}_+.$ Prove that if $G = (V,E)$ is a connected graph with $|E| > {k^k \choose 2},$ then $G$ has a vertex of degree at least $k$ or contains a path with $k$ edges.

It suffices to show that if $G$ does not have a vertex of degree at least $k$, then $G$ contains a path with $k$ edges. However, I'm not sure how to find this path. I tried considering a few small cases such as $k=1,2,$ but I'm not sure how to generalize the result. For instance, for $k=1, G$ clearly contains at least two vertices and a path with $1$ edge (the path between those two distinct vertices). If $k=2, |E| > 6$, and by connectedness of $G$, there must be a vertex of degree at least $k$; if all vertices are of degree one, since $G$ is connected, it can only have two vertices and one edge, but then the number of edges is not more than $6$, a contradiction. I should definitely use the connected property, but I'm not sure how; for $k=2,$ if $G$ is disconnected, the proposition clearly fails.

  • 2
    $\begingroup$ There is no limit on the number of vertices, so for $k=2$ if we abandon the requirement that the graph be connected the graph could be seven disconnected segments, each connecting two vertices. $\endgroup$ – Ross Millikan Oct 30 '20 at 2:44
  • $\begingroup$ What about the number of vertices in $G$? How does that relate to $k$. $\endgroup$ – Mike Oct 30 '20 at 2:45
  • $\begingroup$ Well, certainly if the degree of each vertex is less than $k$, the number of vertices of G must be greater than $\dfrac{k^k}{(k-1)(k^k-2)!}$ by some manipulation of the Handshaking Lemma, but I’m not sure how this helps to prove the result. And it’s easy to show that $k$ must be greater than $1$ if all vertices have degree less than $k$. $\endgroup$ – Fred Jefferson Oct 30 '20 at 2:55
  • $\begingroup$ Because $k^k$ grows so fast and ${k^k \choose 2}$ even faster it seems like the bound is quite loose. If all the vertices are of degree less than $k$ there must be a lot of them. Since the graph is connected it wants to have a long path. The best way I see to avoid a long path is to have a bunch of complete graphs connected in a network, but then you go through one complete graph and go on to the next. Maybe cycles connected to each other work better, but they do not contribute many edges each. Just some musings that might trigger better throughts. $\endgroup$ – Ross Millikan Oct 30 '20 at 2:57

I'll lay out an approach / hint in the first part, and then complete the proof in the second part of the post.

We can assume $k>1$. If $G$ has a vertex of degree $k$, we are done. So we assume that the maximum degree of $G$ is some $\Delta \leq k-1$.

We let $u$ be a vertex of $G$, and assume for the sake of contradiction that $G$ does not contain any path of length $k$. In particular, this means that the diameter of $G$ is at most $k-1$ (since $G$ is connected and has no $k$-path), so every vertex of $G$ is within distance $k-1$ of $u$ (this is where connectivity is useful!).

If you just wanted a hint / way to approach the problem, stop reading here.

Now given the degree and distance constraints we have so far, let's see how many vertices $G$ can have. We introduce the notation:

$$N_i(u) = \{v\in G : d(u,v) = i\}$$ The vertex $u$ has at most $(k-1)$ neighbours at distance $1$ from it (i.e., we have $|N_1(u)| \leq k-1$). Each of these in turn has at most $(k-2)$ neighbours besides $u$. So the set $N_2(u)$ of vertices distance $2$ from $u$ has $|N_2(u)| \leq (k-1)(k-2)$ (see the diagram).

enter image description here

In general, we get that $|N_i(u)| \leq (k-1)(k-2)^{i-1}$. So the total number of vertices $n$ is bounded above as follows:

$$n = |\{u\}| + |N_1(u)| + \dots + |N_{k-1}(u)|$$

And thus:

$$n \leq 1 + (k-1) + (k-1)(k-2) + \dots + (k-1)(k-2)^{k-2} = 1 + (k-1)\sum_{i=0}^{k-2}(k-2)^i$$

By using the formula for the sum of a geometric series, and a bit of inequality juggling, you can show that $n \leq k^k$. Thus the total possible number of edges that $G$ has is at most $\binom{n}{2} \leq \binom{k^k}{2}$. But this yields a contradiction, so $G$ must have a $k$-path.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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