7
$\begingroup$

It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by peeling away low degree vertices, doesn't seem to characterise, in any nice way, the extremal examples for which the constant $1/2$ cannot be improved.

So my question is, what do extremal examples "look like"? Is there a simple characterisation? If not, I'd love to see any interesting constructions/families which give infinitely many extremal examples for a given value of $d$.

Improve this question
$\endgroup$
2
  • $\begingroup$ If $d$ is a positive integer, then a graph with average degree $d$ must actually contain a subgraph with minimum degree at least $\lfloor\frac{d}{2}\rfloor+1>\frac{d}{2}$, so when you say that the constant $\frac{1}{2}$ cannot be improved, you mean asymptotically as $d\to\infty$, right ? But then in the second part of your post you seem to consider $d$ as being fixed. Could you clarify ? $\endgroup$
    – Dr J
    Commented Apr 10, 2014 at 16:12
  • $\begingroup$ I mean asymptotically, of course. When I say $d$ fixed, I mean for large $d$ and infinitely many $n$ (number of vertices) for that $d$, i.e., $d \to \infty$ and for each $d$ in that sequence, an infinite family of graphs on a larger and larger number of vertices of average degree about $d$. Does that clarify what I'm asking for? $\endgroup$
    – BPN
    Commented Apr 10, 2014 at 16:45

4 Answers 4

Reset to default
10
$\begingroup$

If $G$ and $H$ are both extremal graphs (possibly for different values of $d$) then their Cartesian product is another extremal graph for the sum of the degrees. So the grid example is just a Cartesian product of paths, and you can similarly take the Cartesian product of trees.

A much more general way of constructing graphs with this property, which allows some vertices to have high degree: form a sequence of $n$ vertices and connect each vertex arbitrarily to $d/2$ later vertices in the sequence. Then, in any subset of vertices, the first vertex will have degree $d/2$, but (for $n$ sufficiently large relative to $d$) the average degree will be close to $d$.

Improve this answer
$\endgroup$
0
4
$\begingroup$

Grids. (for one example only)

The grid $\overbrace{P_m \Box P_m \Box \cdots \Box P_m}^k$ has average degree about $2k$ as $m \rightarrow \infty$, but any subgraph seems to have to include a "corner" point of degree $\le k$. I haven't thought too hard about how to make this precise.

And sorry: I don't have the graph theory expertise to fully characterize the extremal examples. What seems to make this argument work (provided I'm not wrong) is that the grid has a natural embedding in $\mathbb{R}^k$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! I suspect a complete characterisation might be hopeless to begin with, so every example tells us something. $\endgroup$
    – BPN
    Commented Apr 10, 2014 at 18:05
  • 1
    $\begingroup$ More precise: If we label the vertices by their coordinates in $\{1,2,\dots,m\}^k$, the lexicographically smallest vertex in the subgraph can't have more than $k$ neighbours (otherwise one of them would be lexicographically smaller). $\endgroup$
    – Janne Kokkala
    Commented Apr 11, 2014 at 7:48
4
$\begingroup$

Another class of examples is given by trees. A tree on $n$ vertices has $n-1$ edges, and thus has average degree $2 - 2/n$. However, any subgraph must contain leaves, and thus has minimum degree $1$.

One may make the average/minimum degree arbitrarily large by `blowing up' the tree: replace every vertex with an independent set of size $d$, and replacing every edge of the tree by a complete bipartite graph $K_{d,d}$ on the vertices of the independent sets corresponding to the endpoints of the edge. This blow-up now has $nd$ vertices and $(n-1)d^2$ edges, and so has average degree $2d - 2d/n$. However, in any subgraph the vertices from the independent sets corresponding to leaves can have degree at most $d$.

My initial construction for an example with large minimum degree was the complete unbalanced bipartite graph $K_{\alpha n,n}$ for $\alpha \rightarrow 0$, but this corresponds to the blow-up of the tree $K_{1,1/\alpha}$ (by the factor $d = \alpha n$).

I am afraid I do not have a more general answer at this point!

Improve this answer
$\endgroup$
3
  • $\begingroup$ For $d=1$ this construction is optimal, in that any graph on $n$ vertices with max-min subgraph degree $1$ and average degree at least $2-2/n$ is a tree. (Proof: must have no cycles, so a forest, so by second condition a tree.) I wonder if your construction gives all examples on $nd$ vertices with min-max subgraph degree $n$ and average degree at least $2d-d/n$. $\endgroup$
    – Will Sawin
    Commented Apr 10, 2014 at 22:04
  • $\begingroup$ I'm afraid this is fair from optimal! The blow-up of trees to $N$ vertices has average degree $2d - 2d^2/N$. On the other hand, if we follow David Eppstein's construction (which, as shown by JDRS, gives the required characterisation), we can get more edges: The first $N-d$ vertices each send $d$ forward edges. The last $d$ vertices cannot send as many edges forward, but may form a complete graph. This gives $(N-d)d + {d \choose 2}$ edges, resulting in an average degree of $2d - (d+1)/N$. It was just a happy coincidence that $d+1 = 2d^2$ when $d=1$! $\endgroup$
    – Shagnik
    Commented Apr 11, 2014 at 13:56
  • $\begingroup$ Also, a small remark on the proof of JDRS (I have not yet acquired a sufficient reputation to comment on it directly). In the proof, we only used the fact that $\epsilon(i) \le \epsilon$, not $|\epsilon(i)| \le \epsilon$. The weaker condition allows the last few vertices to have low forward-degree without worrying about boundary conditions separately. The average degree then follows by counting only the forward edges. The condition $\sum_i \epsilon(i) = 0$ guarantees the average degree is precisely $d$. $\endgroup$
    – Shagnik
    Commented Apr 11, 2014 at 14:05
4
$\begingroup$

I believe that David Eppstein's construction is basically the whole story. So for $0 <\epsilon \leq 1/2 $, call a graph 'bad' if it fails to have a subgraph with min degree $> (1/2 +\epsilon)d$.

Now Eppstein's construction restated:

" Build a graph on $1,...,n$ by visiting each vertex $i= 1,2.. $ and, at each stage, join $i$ to $(1/2 + \epsilon(i))d $ additional vertices among $\{ i+1, \ldots ,n \} $"

Where $|\epsilon(i)| \leq \epsilon$ and $\sum \epsilon(i) = 0$. One thinks of this $\epsilon(i)$ as the 'noise' allowed by the $\epsilon$-room that we have.

The average vertex has $d/2$ neighbors ahead of it and was hit by $d/2$ edges from previous vertices so the average degree is $d$. Of course, there are some issues at the boundary but this does not affect the average if we take n large.

Now we show that every 'bad' graph is constructed in this way. Obverse that bad graphs are the ones that are reduced to the empty graph by the process:

"If there is a vertex of degree $\leq (1/2 + \epsilon)d$ remove it. Otherwise, STOP".

Thus for a bad graph,we get an ordering of the vertices $v_1,v_2,...,v_n$ (taking in the order removed by the process) so that $v_i$ has at most $(1/2 + \epsilon)d$ edges forward to $v_{i+1}, \ldots v_n$. If the number of forward edges of $v_i$ is $(1/2 + \epsilon(i))d$ then $\sum \epsilon(i)=0$ holds by the fact the average degree is $d$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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