5
$\begingroup$

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!

Improve this question
$\endgroup$
8
  • $\begingroup$ Their neighborhood can be different, in your proof you didn't consider neighborhood connectivity. $\endgroup$
    – Saeed
    Commented Mar 29, 2014 at 21:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Mar 29, 2014 at 23:00
  • $\begingroup$ 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). $\endgroup$
    – Saeed
    Commented Mar 30, 2014 at 18:42
  • $\begingroup$ @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. $\endgroup$
    – Vivek Bagaria
    Commented Mar 31, 2014 at 10:28
  • $\begingroup$ 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. $\endgroup$
    – Vivek Bagaria
    Commented Mar 31, 2014 at 10:32

2 Answers 2

Reset to default
1
$\begingroup$

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.
Improve this answer
$\endgroup$
7
  • $\begingroup$ I think he looks for subgraph as he stated not induced one. $\endgroup$
    – Saeed
    Commented Mar 29, 2014 at 23:08
  • 2
    $\begingroup$ As Saeed pointed out, I am looking for a subgraph not an induced subgraph. $\endgroup$
    – Vivek Bagaria
    Commented Mar 30, 2014 at 15:13
  • $\begingroup$ @Bagaria thanks. Do you also desire a subgraph of "sufficient size" ? $\endgroup$
    – Suresh Venkat
    Commented Mar 31, 2014 at 5:24
  • $\begingroup$ @SureshVenkat: Yes, I wanted the size of the subgraph to be to be a constant times the size of the original graph. $\endgroup$
    – Vivek Bagaria
    Commented Mar 31, 2014 at 10:39
  • 2
    $\begingroup$ @Bagaria then add this condition to your question. $\endgroup$
    – Saeed
    Commented Mar 31, 2014 at 10:44
1
$\begingroup$

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).

Improve this answer
$\endgroup$
6
  • $\begingroup$ The question didn't ask for regular subgraphs (it's really different situation). $\endgroup$
    – Saeed
    Commented Apr 2, 2014 at 14:23
  • $\begingroup$ 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. $\endgroup$
    – Aravind
    Commented Apr 3, 2014 at 10:54
  • $\begingroup$ Every graph contains a regular subgraph, consider a subgraph which obtained by deleting all edges. $\endgroup$
    – Saeed
    Commented Apr 3, 2014 at 10:57
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Apr 3, 2014 at 11:00
  • $\begingroup$ 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. $\endgroup$
    – Aravind
    Commented Apr 3, 2014 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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