Wikipedia:Reference desk/Archives/Mathematics/2016 February 6

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 6

question in graph theory

Hi,
Suppose we have a graph $G$ where $|V(G)|\geq k+1$ ($k\in \mathbb {N}$), and for all two non-neighbors vertices it holds that $d(u)+d(v)\geq 2k$. How can we prove that the average degree of this graph is at least $k$?
Tnanks — Preceding unsigned comment added by 217.132.96.145 (talk) 19:51, 6 February 2016 (UTC)

Just sum over all vertices, and show that the sum is greater than $|V|\cdot 2k$.

The idea is to sum over couples of non-neighbors vertices.

If all the vertices in the graph are neighbors, we're done, since $|V|\geq k+1$, so each node has degree $\geq k$.

Also, if all the vertices have degree $\geq k$, we're done.

Otherwise, there're at least 2 non-neighbors vertices, v and u, that one of which has degree<k, and the second has degree>k.

We know that $d(u)+d(v)\geq 2k$. WLOG $d(v)>d(u)$. So, $d(v)\geq k+1$

Now, for every vertex, u, which is not a neighbor of v, it holds that $d(u)+d(v)\geq 2k$. So, $d(u)\geq 2k-n$.

Now, we remain only with the neighbors of v.

If they're all neighbors, then we know that their degree $\geq n-1\geq k$.

Otherwise, there are two vertices that are not neighbors - fix one of which and continue this way recursively.

Since the statement (that the average of the degrees over the fixed vertex and its non-neighbors vertices is >= k) holds all the time during the recursion, so the statement is correct.

Notice that this method of recursion is similar to inducion, that you're probably more familiar with. עברית (talk) 10:39, 8 February 2016 (UTC)

I'm not clear on everything here but I'm pretty sure there is a flaw in this argument. The statement that there must be a pair of non-neighbors u and v with d(u)<k and d(v)>k does not follow; take k=3 and consider the complete bipartite graph K_2,4. Also note that you only need to show that the sum of the degrees is at least |V|k, not 2|V|k. --RDBury (talk) 22:43, 8 February 2016 (UTC)

Here's what I came up with. First, to simplify notation, let n=|V| = number of vertices in G, and let s be the degree sum = twice the number of edges. So

$s=\sum _{u}d(u).$

We need to show s≥kn. Write

$sn=\sum _{v}d(v)\sum _{u}1=\sum _{u,v}d(u)$

so

$2sn=\sum _{u,v}(d(u)+d(v)).$

Split this sum according to u=v, u adjacent to v and u not adjacent to v. I'll use $\sim$ and $\nsim$ for adjacent and non-adjacent. (Is there a standard notation for this or do graph theorists have to write "adjacent" all the time?)

$2sn=\sum _{u=v}(d(u)+d(v))+\sum _{u\sim v}(d(u)+d(v))+\sum _{u\nsim v}(d(u)+d(v)).$

The first sum is simply

$\sum _{u}2d(u)=2s.$

The second sum is

$\sum _{u\sim v}(d(u)+d(v))=2\sum _{u\sim v}d(u)=2\sum _{u}d(u)^{2}\geq {\frac {2}{n}}\left(\sum _{u}d(u)\right)^{2}={\frac {2s^{2}}{n}}$

by a well known inequality I can't remember the name of at the moment. (Please fill this in if you know.) There are n²-n-s terms in the third sum so by assumption this is

$\sum _{u\nsim v}(d(u)+d(v))\geq 2k(n^{2}-n-s).$

Putting this together gives

$2sn\geq 2s+{\frac {2s^{2}}{n}}+2k(n^{2}-n-s)$

$sn^{2}\geq sn+s^{2}+kn(n^{2}-n-s)$

$sn^{2}-sn-s^{2}-kn(n^{2}-n-s)\geq 0$

$(s-kn)(n^{2}-n-s)\geq 0.$

As pointed out above, there must be at least one non-edge so

$n^{2}-n-s>0$

and so

$s-kn\geq 0.$

Note, the inequality used above is strict unless the d(u)'s are all equal, so the average degree is strictly greater than k unless G is k-regular. --RDBury (talk) 00:30, 9 February 2016 (UTC)

Re the inequality used above, the Cauchy–Schwarz inequality says

$\left(\sum _{i=1}^{n}x_{i}y_{i}\right)^{2}\leq \sum _{j=1}^{n}{x_{j}}^{2}\sum _{k=1}^{n}{y_{k}}^{2}$

and with y_i≡1 this is

$\left(\sum _{i=1}^{n}x_{i}\right)^{2}\leq n\sum _{i=1}^{n}{x_{i}}^{2},$

but I thought there was another name for this special case. --RDBury (talk) 00:57, 9 February 2016 (UTC)

Thank you all! — Preceding unsigned comment added by 217.132.96.145 (talk) 16:38, 10 February 2016 (UTC)