1
$\begingroup$

If a graph has large minimum degree, i.e. everywhere, locally, many edges per vertex, it also has many edges per vertex globally: $\varepsilon(G)=$ $\frac{1}{2} d(G) \geqslant \frac{1}{2} \delta(G)$. Conversely, of course, its average degree may be large even when its minimum degree is small. However, the vertices of large degree cannot be scattered completely among vertices of small degree: as the next proposition shows, every graph $G$ has a subgraph whose average degree is no less than the average degree of $G$, and whose minimum degree is more than half its average degree:।

Proposition 1.2.2. Every graph $G$ with at least one edge has a subgraph $H$ with $\delta(H)>\varepsilon(H) \geqslant \varepsilon(G)$.

Proof. To construct $H$ from $G$, let us try to delete vertices of small degree one by one, until only vertices of large degree remain. Up to which degree $d(v)$ can we afford to delete a vertex $v$, without lowering $\varepsilon$ ? Clearly, up to $d(v)=\varepsilon$ : then the number of vertices decreases by 1 and the number of edges by at most $\varepsilon$, so the overall ratio $\varepsilon$ of edges to vertices will not decrease.

Formally, we construct a sequence $G=G_{0} \supseteq G_{1} \supseteq \ldots$ of induced subgraphs of $G$ as follows. If $G_{i}$ has a vertex $v_{i}$ of degree $d\left(v_{i}\right) \leqslant \varepsilon\left(G_{i}\right)$, we let $G_{i+1}:=G_{i}-v_{i}$; if not, we terminate our sequence and set $H:=G_{i}$. By the choices of $v_{i}$ we have $\varepsilon\left(G_{i+1}\right) \geqslant \varepsilon\left(G_{i}\right)$ for all $i$, and hence $\varepsilon(H) \geqslant \varepsilon(G)$.

What else can we say about the graph $H$ ? Since $\varepsilon\left(K^{1}\right)=0<\varepsilon(G)$, none of the graphs in our sequence is trivial, so in particular $H \neq \emptyset$. The fact that $H$ has no vertex suitable for deletion thus implies $\delta(H)>\varepsilon(H)$, as claimed.

Precisely, what does it mean by saying "the vertices of large degree cannot be scattered completely among vertices of small degree"?

If I were to take the subgraph containing the largest degree vertex and its neighbors, then this would certainly have a larger minimum degree than the average degree of the original graph. Wouldn't this be all that is needed to imply there is no way to "drown out" the large degree vertices? Because a high degree vertex surrounded by many many small degree vertex is still a high degree vertex in the graph...

$\endgroup$

1 Answer 1

2
$\begingroup$

Precisely, what does it mean by saying "the vertices of large degree cannot be scattered completely among vertices of small degree"?

This means that you must have vertices of high degree - specifically, higher than $\varepsilon(G)$ - that are adjacent to each other. The high degree vertices cannot only have low degree neighbors.

If I were to take the subgraph containing the largest degree vertex and its neighbors, then this would certainly have a larger minimum degree than the average degree of the original graph.

This is not true. Consider the Mycielskian graph $M_4$, in the picture below. The vertex of maximum degree (5) has a neighborhood which induces a star, having average degree less than 2. The graph as a whole however has average degree strictly greater than 3.

Picture of $M_4$ from wikipedia:

enter image description here

$\endgroup$
5
  • $\begingroup$ You say "The high degree vertices cannot only have low degree neighbors". But what about a star? this is one high degree vertex with only low degree neighbors. $\endgroup$ Jun 18, 2022 at 19:43
  • $\begingroup$ Here "high" means "greater than $\varepsilon(G)$". In the case of a star, $\varepsilon(G)$ is very low (it's less than 1). So ALL the vertices have "high" degree, which means that every high degree vertex has high degree neighbors. This odd situation only occurs because a star has very few edges. In graphs with lots of edges distributed unevenly, the phenomenon becomes more meaningful. $\endgroup$ Jun 18, 2022 at 19:59
  • $\begingroup$ Ah it makes sense now! Why is $\epsilon(G)=\frac{|E|}{|V|}$ used and not $\delta(G)=\frac{1}{|V|}\sum_{v\in V}\text{deg}(V)$ to define what a high-degree vertex is? $\endgroup$ Jun 18, 2022 at 20:02
  • $\begingroup$ We use that to define what we mean by "high degree" or "large degree" because of the Proposition you have quoted in your post. Besides, these two quantities are exactly the same up to a factor of 2. $\endgroup$ Jun 18, 2022 at 20:07
  • 1
    $\begingroup$ Thank you so much for your help! I understand now $\endgroup$ Jun 18, 2022 at 20:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .