<p>This is not possible. Not every graph contains a "nearly regular" subgraph with large average degree.</p>

<p>The explanation given below is from the paper "Every graph of sufficiently large average degree contains a $C_4$-free subgraph of large degree" by Daniela Kuhn and Deryk Osthus.</p>

<p>In the paper "Dense subgraphs without 3-regular subgraphs", Pyber, Rodl and Szemeredi prove that:</p>

<p>(i) Any graph with at least $c_k n \log (\Delta)$ edges contains a $k$-regular subgraph;</p>

<p>(ii) There exist graphs on $\Omega(n \log \log n)$ edges which do not contain a $k$-regular subgraph for every $k \geq 3$.</p>

<p>If the answer to your question was yes, then the subgraph $G'$ would satisfy (i) with any constant $k$ (for sufficiently large $\Delta(G)$), and hence contain a $k$-regular subgraph - this contradicts (ii).</p>

CC BY-SA 3.0
2014-04-02T14:23:52.597Z
The question didn't ask for regular subgraphs (it's really different situation).
Saeed
CC BY-SA 3.0
2014-04-03T10:54:36.953Z
The question asks for a subgraph all of whose vertices have degrees between $c_1d(G)$ and $c_2d(G)$, i.e. a graph which is "nearly regular". The argument is that (i) a "nearly regular" graph must contain a regular subgraph; (ii) not all graphs can contain regular subgraphs. Thus, not all graphs can contain a "nearly regular" subgraph.
Aravind
CC BY-SA 3.0
2014-04-03T10:57:34.230Z
Every graph contains a regular subgraph, consider a subgraph which obtained by deleting all edges.
Saeed
CC BY-SA 3.0
2014-04-03T11:00:53.693Z
Also if for every $k>2$ there exists a graph that does not contain k-regular subgraph doesn't mean there exists no k-1 or k/2, k+1,  .... regular subgraph on that graph, there are lots of similar things in your argument that makes it absolutely wrong.
Saeed
CC BY-SA 3.0
2014-04-03T20:25:17.923Z
I have edited (ii) of my answer; the earlier statement while true, was my mistake. In my earlier comment, I meant regular subgraphs with regularity at least 3.
Aravind
CC BY-SA 3.0
2014-04-03T20:57:11.327Z
Right now makes sense, it's better to also provide a link to papers then OP can verify correctness of your argument.
Saeed
CC BY-SA 3.0
2014-04-02T14:11:01.383Z
2014-04-03T20:23:52.983Z
2014-04-03T20:23:52.983Z
Aravind
<p>If you want to find an <strong>induced</strong> subgraph of "sufficient size" i.e not of constant size, then this is not possible. Consider the star $K_{1, n}$, which has average degree $2-1/n$.  Take any subset of the vertices. </p>

<ul>
<li>if the subset contains the central node, then the max degree equals the size of the subset. If this subset is more than a constant size, then it violates your condition.</li>
<li>if the subset does not contain the central node then the max degree is zero, which again violates your condition.</li>
</ul>

CC BY-SA 3.0
2014-03-29T23:08:37.703Z
I think he looks for subgraph as he stated not induced one.
Saeed
CC BY-SA 3.0
2014-03-30T15:13:32.943Z
As Saeed pointed out, I am looking for a subgraph not an induced subgraph.
Vivek Bagaria
CC BY-SA 3.0
2014-03-31T05:24:39.330Z
@Bagaria thanks. Do you also desire a subgraph of "sufficient size" ?
Suresh Venkat
CC BY-SA 3.0
2014-03-31T10:39:41.023Z
@SureshVenkat: Yes, I wanted the size of the subgraph to be to be a constant times the size of the original graph.
Vivek Bagaria
CC BY-SA 3.0
2014-03-31T10:44:56.107Z
@Bagaria then add this condition to your question.
Saeed
CC BY-SA 3.0
2014-04-02T15:15:09.273Z
@Saeed, the star graph still serves to constrain $c_2$ to be either $0$ or $n/(2n-2)$, which is a fairly effective negative answer to the question.
Peter Taylor
CC BY-SA 3.0
2014-04-02T15:45:00.363Z
@PeterTaylor, Satisfying any of that two condition is easy but both together is hard. Also I think you want to mention OP not me (I have nothing to do with this problem except that I tried to provide counter example for it and I failed, also if you talking about my last comment, I know if there is a counter example then that example should satisfy OPs latest requirement, and I can prove it, but the question should be self contained).
Saeed
CC BY-SA 3.0
2014-03-29T23:05:47.097Z
2014-03-29T23:05:47.097Z
Suresh Venkat
<p>Consider a graph $G$ with max degree $\Delta_G$, min degree $\delta_G$ and average degree $d_G$. </p>

<p>Is it possible to obtain a subgraph of $G$, say $G'$, such that  $\Delta_{G'} = c_1d_{G}$, $\delta_{G'} = c_2d_{G}$ , where $c_1,c_2$ are constants</p>

<p><strong>EDIT 1</strong>: Also the size of the resultant subgraph $G'$ must be constant times the size of original graph $G$.</p>

<p><strong>My attempt :</strong> </p>

<p>Let $X$ be the random variable which denotes the degree of any randomly chosen vertex. Therefore, $d_G = E[X]$. Using markovs's inequality, we have</p>

<p>$$P(X &gt; 3E[X]) &lt; \frac{1}{3} $$
 and 
$$P(X &lt; \frac{E[X]}{3}) = P(\frac{1}{X} &gt; \frac{3}{E[X]}) &lt; \frac{E[\frac{1}{X}]*E[X]}{3} &lt; \frac{1}{3}$$</p>

<p>Using union bound, we have</p>

<p>$$P(\frac{E[X]}{3} &lt; X &lt; 3E[X]) &gt; 1/3$$.</p>

<p>Using the above equation, we can show that there exist $|V|/3$ vertices in $G$ whose degree is between $d_G/3$ and $3d_G$.</p>

<p>Does the graph obtained by the above $|V|/3$ vertices solve the problem? If not, can we modify the technique to obtain a solution?</p>

<p>Thanks in advance!</p>

CC BY-SA 3.0
2014-03-29T21:49:34.180Z
Their neighborhood can be different, in your proof you didn't consider neighborhood connectivity.
Saeed
CC BY-SA 3.0
2014-03-29T23:00:15.033Z
Just because there are enough vertices with the desired property doesn't mean that the associated induced subgraph has the same properties: because maybe I'm a vertex in your set, but my degree comes from connections to vertices that are NOT in your set.
Suresh Venkat
CC BY-SA 3.0
2014-03-30T18:42:04.000Z
I tried to subdivide edges of some dense graph in such a way that average degree be $f(|G|)$ and violating a condition in both side (by providing some gadget). It didn't work and I thought about this may be around 1 hour (it was really interesting question to me), I mean even if there is a counter example, then it's not easy to find one, and currently my guess is in reverse direction of my first comment. I think is possible to find such a subgraph but sure this proof lacks very much (may be someday if I look back to this problem I have another opinion).
Saeed
CC BY-SA 3.0
2014-03-31T10:28:54.207Z
@Saeed: I understood the flaw in my proof by your first comment. But here is a possible extension of this proof to obtain the desired subgraph.
Vivek Bagaria
CC BY-SA 3.0
2014-03-31T10:32:10.887Z
Currently we are bound the degree of the vertices between d/3 and 3d. If the current subgraph doesn't satisfy the desired result, we keep increasing the the upper bound or keep decreasing the lower bound until the graph satisfies the required properties. This idea is not complete and for all we know, it might not be a solution! But this path is worth exploring.
Vivek Bagaria
CC BY-SA 3.0
2014-03-31T10:43:42.287Z
@Bagaria, Probably that works, I'll also think about it in my free time.
Saeed
CC BY-SA 3.0
2014-03-31T20:50:59.007Z
Why not just pick edges at random ?
Suresh Venkat
CC BY-SA 3.0
2014-04-01T03:55:16.460Z
@SureshVenkat: I tried the method of picking edges at random, but then I couldn't get any good bound on the vertex degree.
Vivek Bagaria
<graph-theory><pr.probability>
Subgraph of G whose maximum degree and minimum degree are of the same order
Vivek Bagaria
# Subgraph of G whose maximum degree and minimum degree are of the same order

(Asked by: username_0 on 2014-03-29)

Consider a graph $G$ with max degree $\Delta\_G$, min degree $\delta\_G$ and average degree $d\_G$.

Is it possible to obtain a subgraph of $G$, say $G'$, such that $\Delta\_{G'} = c\_1d\_{G}$, $\delta\_{G'} = c\_2d\_{G}$ , where $c\_1,c\_2$ are constants

**EDIT 1**: Also the size of the resultant subgraph $G'$ must be constant times the size of original graph $G$.

**My attempt :**

Let $X$ be the random variable which denotes the degree of any randomly chosen vertex. Therefore, $d\_G = E[X]$. Using markovs's inequality, we have

$$P(X > 3E[X]) < \frac{1}{3} $$
and
$$P(X < \frac{E[X]}{3}) = P(\frac{1}{X} > \frac{3}{E[X]}) < \frac{E[\frac{1}{X}]\*E[X]}{3} < \frac{1}{3}$$

Using union bound, we have

$$P(\frac{E[X]}{3} < X < 3E[X]) > 1/3$$.

Using the above equation, we can show that there exist $|V|/3$ vertices in $G$ whose degree is between $d\_G/3$ and $3d\_G$.

Does the graph obtained by the above $|V|/3$ vertices solve the problem? If not, can we modify the technique to obtain a solution?

Thanks in advance!

**Tags:** graph-theory, pr.probability
> **Comments:**
> **username_1**: Their neighborhood can be different, in your proof you didn't consider neighborhood connectivity.  
> **username_2**: Just because there are enough vertices with the desired property doesn't mean that the associated induced subgraph has the same properties: because maybe I'm a vertex in your set, but my degree comes from connections to vertices that are NOT in your set.  
> **username_1**: I tried to subdivide edges of some dense graph in such a way that average degree be $f(|G|)$ and violating a condition in both side (by providing some gadget). It didn't work and I thought about this may be around 1 hour (it was really interesting question to me), I mean even if there is a counter example, then it's not easy to find one, and currently my guess is in reverse direction of my first comment. I think is possible to find such a subgraph but sure this proof lacks very much (may be someday if I look back to this problem I have another opinion).  
> **username_0**: @Saeed: I understood the flaw in my proof by your first comment. But here is a possible extension of this proof to obtain the desired subgraph.  
> **username_0**: Currently we are bound the degree of the vertices between d/3 and 3d. If the current subgraph doesn't satisfy the desired result, we keep increasing the the upper bound or keep decreasing the lower bound until the graph satisfies the required properties. This idea is not complete and for all we know, it might not be a solution! But this path is worth exploring.  
> **username_1**: @Bagaria, Probably that works, I'll also think about it in my free time.  
> **username_2**: Why not just pick edges at random ?  
> **username_0**: @SureshVenkat: I tried the method of picking edges at random, but then I couldn't get any good bound on the vertex degree.  

---

## 2 answers

### Answer by username_3 on 2014-04-02. Score: 1

This is not possible. Not every graph contains a "nearly regular" subgraph with large average degree.

The explanation given below is from the paper "Every graph of sufficiently large average degree contains a $C\_4$-free subgraph of large degree" by Daniela Kuhn and Deryk Osthus.

In the paper "Dense subgraphs without 3-regular subgraphs", Pyber, Rodl and Szemeredi prove that:

(i) Any graph with at least $c\_k n \log (\Delta)$ edges contains a $k$-regular subgraph;

(ii) There exist graphs on $\Omega(n \log \log n)$ edges which do not contain a $k$-regular subgraph for every $k \geq 3$.

If the answer to your question was yes, then the subgraph $G'$ would satisfy (i) with any constant $k$ (for sufficiently large $\Delta(G)$), and hence contain a $k$-regular subgraph - this contradicts (ii).

> **Comments:**
> **username_1**: The question didn't ask for regular subgraphs (it's really different situation).  
> **username_3**: The question asks for a subgraph all of whose vertices have degrees between $c_1d(G)$ and $c_2d(G)$, i.e. a graph which is "nearly regular". The argument is that (i) a "nearly regular" graph must contain a regular subgraph; (ii) not all graphs can contain regular subgraphs. Thus, not all graphs can contain a "nearly regular" subgraph.  
> **username_1**: Every graph contains a regular subgraph, consider a subgraph which obtained by deleting all edges.  
> **username_1**: Also if for every $k>2$ there exists a graph that does not contain k-regular subgraph doesn't mean there exists no k-1 or k/2, k+1,  .... regular subgraph on that graph, there are lots of similar things in your argument that makes it absolutely wrong.  
> **username_3**: I have edited (ii) of my answer; the earlier statement while true, was my mistake. In my earlier comment, I meant regular subgraphs with regularity at least 3.  
> **username_1**: Right now makes sense, it's better to also provide a link to papers then OP can verify correctness of your argument.  

---

### Answer by username_2 on 2014-03-29. Score: 1

If you want to find an **induced** subgraph of "sufficient size" i.e not of constant size, then this is not possible. Consider the star $K\_{1, n}$, which has average degree $2-1/n$. Take any subset of the vertices.

* if the subset contains the central node, then the max degree equals the size of the subset. If this subset is more than a constant size, then it violates your condition.
* if the subset does not contain the central node then the max degree is zero, which again violates your condition.

> **Comments:**
> **username_1**: I think he looks for subgraph as he stated not induced one.  
> **username_0**: As Saeed pointed out, I am looking for a subgraph not an induced subgraph.  
> **username_2**: @Bagaria thanks. Do you also desire a subgraph of "sufficient size" ?  
> **username_0**: @SureshVenkat: Yes, I wanted the size of the subgraph to be to be a constant times the size of the original graph.  
> **username_1**: @Bagaria then add this condition to your question.  
> **username_4**: @Saeed, the star graph still serves to constrain $c_2$ to be either $0$ or $n/(2n-2)$, which is a fairly effective negative answer to the question.  
> **username_1**: @PeterTaylor, Satisfying any of that two condition is easy but both together is hard. Also I think you want to mention OP not me (I have nothing to do with this problem except that I tried to provide counter example for it and I failed, also if you talking about my last comment, I know if there is a counter example then that example should satisfy OPs latest requirement, and I can prove it, but the question should be self contained).  

---

