Return to Answer

added 2 characters in body

Source Link

edited Aug 1, 2022 at 3:53

20.2k
3
43
126

Proof 1 of Statement B for regular graphs. Let $\Gamma$ be a regular graph of degree $d$. As in F. Petrov's answer to Existence of connected component with large boundary? : by Kleitman and West (https://epubs.siam.org/doi/10.1137/0404010), there exists a spanning tree with $\geq n/4$ leaves, where $n=|V|$. Define $S$ to be the set of non-leaves. Then the total degree of the elements of $V\setminus S$ (that is, the leaves) is $\geq d n/4 = N/4$$\geq d n/4 = |E|/4$.

Proof 2 of Statement B for regular graphs (from scratch, inspired by Kleitman-West - TL;DR greedy algorithm). I thought I had a different proof, but I no longer do, or rather, the proof, when corrected, is not really different from Kleitman-West after all.

More to the point: it seems that a proof along these lines is not going to generalize easily to the non-regular case. It is clear that, for $\Gamma$ not regular, the greedy algorithm could incur a loss at some point and fail to recoup it for more than $C$ steps, for any absolute constant $C$: consider a complete graph of high degree surrounded by many layers of vertices of low degree.

Proof 1 of Statement B for regular graphs. Let $\Gamma$ be a regular graph of degree $d$. As in F. Petrov's answer to Existence of connected component with large boundary? : by Kleitman and West (https://epubs.siam.org/doi/10.1137/0404010), there exists a spanning tree with $\geq n/4$ leaves, where $n=|V|$. Define $S$ to be the set of non-leaves. Then the total degree of the elements of $V\setminus S$ (that is, the leaves) is $\geq d n/4 = N/4$.

Proof 2 of Statement B for regular graphs (from scratch, inspired by Kleitman-West - TL;DR greedy algorithm). I thought I had a different proof, but I no longer do, or rather, the proof, when corrected, is not really different from Kleitman-West after all.

More to the point: it seems that a proof along these lines is not going to generalize easily to the non-regular case. It is clear that, for $\Gamma$ not regular, the greedy algorithm could incur a loss at some point and fail to recoup it for more than $C$ steps, for any absolute constant $C$: consider a complete graph of high degree surrounded by many layers of vertices of low degree.

Proof 1 of Statement B for regular graphs. Let $\Gamma$ be a regular graph of degree $d$. As in F. Petrov's answer to Existence of connected component with large boundary? : by Kleitman and West (https://epubs.siam.org/doi/10.1137/0404010), there exists a spanning tree with $\geq n/4$ leaves, where $n=|V|$. Define $S$ to be the set of non-leaves. Then the total degree of the elements of $V\setminus S$ (that is, the leaves) is $\geq d n/4 = |E|/4$.

Proof 2 of Statement B for regular graphs (from scratch, inspired by Kleitman-West - TL;DR greedy algorithm). I thought I had a different proof, but I no longer do, or rather, the proof, when corrected, is not really different from Kleitman-West after all.

More to the point: it seems that a proof along these lines is not going to generalize easily to the non-regular case. It is clear that, for $\Gamma$ not regular, the greedy algorithm could incur a loss at some point and fail to recoup it for more than $C$ steps, for any absolute constant $C$: consider a complete graph of high degree surrounded by many layers of vertices of low degree.

Source Link

created Jul 28, 2022 at 1:08

20.2k
3
43
126

Proof 1 of Statement B for regular graphs. Let $\Gamma$ be a regular graph of degree $d$. As in F. Petrov's answer to Existence of connected component with large boundary? : by Kleitman and West (https://epubs.siam.org/doi/10.1137/0404010), there exists a spanning tree with $\geq n/4$ leaves, where $n=|V|$. Define $S$ to be the set of non-leaves. Then the total degree of the elements of $V\setminus S$ (that is, the leaves) is $\geq d n/4 = N/4$.

Proof 2 of Statement B for regular graphs (from scratch, inspired by Kleitman-West - TL;DR greedy algorithm). I thought I had a different proof, but I no longer do, or rather, the proof, when corrected, is not really different from Kleitman-West after all.

More to the point: it seems that a proof along these lines is not going to generalize easily to the non-regular case. It is clear that, for $\Gamma$ not regular, the greedy algorithm could incur a loss at some point and fail to recoup it for more than $C$ steps, for any absolute constant $C$: consider a complete graph of high degree surrounded by many layers of vertices of low degree.