2
$\begingroup$

I am trying to prove something, and it will help e greatly to show that the maximum degree of any vertex, $d$ is a connected simple graph, goes up asymptotically linearly along with the number of edges in the graph.

I came up with a somewhat hand-wavey "proof", and I wonder if it is anywhere near correct:

For fixed $|V|=n$, as $m$ grows, so does $d$, linearly, with constant average $\frac{1}{n}$, as by the pigeonhole principle, for every addition of n edges, the maximum degree has to increase by at least 1.


The other direction is easily $m \le \frac{dn}{2}$.


I wonder if this is at all correct, and if so, how to improve the proof

$\endgroup$
2
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Jul 2 '21 at 19:59
  • $\begingroup$ @D.W. about checking my work - well, I study from home, with no friends also studying these subject, and I prefer keeping the few times I allow myself to trouble my single lecturer to harder or more pressing issues. Regarding the request to edit - Please tell me if a better wording would be "How does the maximum degree in a graph asymptotically behaves w.r.t |E|"? In the future I will try to make questions more general. I saw this one as a question + here is my try. $\endgroup$
    – Gulzar
    Jul 2 '21 at 22:02
1
$\begingroup$

The idea is correct. Indeed, if $d$ is the maximal degree in the graph, $n$ is the number of nodes and $m$ is the number of edges, we can give the following bounds on $d$: Define $d_v$ to be the degree of $v$, for any node $v\in V$.

  1. $d\le \min\{m,n\}$
  2. $\lfloor\frac{2m}{n}\rfloor \le d$

The first bound is given by the fact that $d$ has at most $\min \{m,n\}$ edges. This is the correct way to bound $d$ from above, and in fact is the tightest bound we can give.

The second bound is actually the bound you proved (which is the interesting bound), using the pigeonhole principle. The "correct" way to use the pigeonhole principle is to use its extended version. Say there are $m$ edges, then the sum of the degrees is $2m$. We distribute them into $n$ nodes, to get that at least one node has to have degree at least $\lfloor\frac{2m}{n}\rfloor$. The maximal degree has to be at least as big, hence $d\ge \lfloor \frac{2m}{n}\rfloor$.

$\endgroup$

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.