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!

$\endgroup$
  • $\begingroup$ Their neighborhood can be different, in your proof you didn't consider neighborhood connectivity. $\endgroup$ – Saeed Mar 29 '14 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 Mar 29 '14 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 Mar 30 '14 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 Mar 31 '14 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 Mar 31 '14 at 10:32
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.
$\endgroup$
  • $\begingroup$ I think he looks for subgraph as he stated not induced one. $\endgroup$ – Saeed Mar 29 '14 at 23:08
  • 2
    $\begingroup$ As Saeed pointed out, I am looking for a subgraph not an induced subgraph. $\endgroup$ – Vivek Bagaria Mar 30 '14 at 15:13
  • $\begingroup$ @Bagaria thanks. Do you also desire a subgraph of "sufficient size" ? $\endgroup$ – Suresh Venkat Mar 31 '14 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 Mar 31 '14 at 10:39
  • 2
    $\begingroup$ @Bagaria then add this condition to your question. $\endgroup$ – Saeed Mar 31 '14 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).

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

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.