<p>The sum of all degrees $d(x)$ in a graph is at most $2e$. The sum of all $d(x)^{\alpha}$ is at most $(max degree)^{\alpha -1}$ times sum of all $d(x)$. Together these give the upper bound.</p>

CC BY-SA 3.0
2015-05-27T04:00:14.090Z
2015-05-27T04:00:14.090Z
Ryan Williams
<p>I was going over this <a href="http://theory.stanford.edu/~virgi/cs267/papers/klokskratschmuller.pdf">paper</a> and I don't understand a certain proof (section five phase 2).</p>

<p>Given a graph <em>G=(V,E)</em> partitioned into the sets of vertices <em>L</em> and <em>H</em>. The vertices in <em>L</em> are at most <em>D</em> where <em>D</em> is an arbitrary number and the rest of the vertices are in <em>H</em>.</p>

<p>If we take a closer look at Phase 2 (Theorem 5). For each vertex <em>x</em> in <em>L</em> compute the square of the adjacency matrix of <em>G[N(x)]</em> to decide whether <em>G[N(x)]</em> contains a triangle. </p>

<p>We know that the fastest way to find a triangle in a graph is using fast matrix multiplication algorithm which is $O(n^\alpha)$. So, we can define a running time of $\sum_{x \epsilon L}^{ } d(x)^\alpha$. Since we know that <em>|L|</em> can be at most <em>e</em> (number of edges) if we choose a bad <em>D</em> and <em>d(x)</em> is at most <em>D</em>, why Phase 2 can be done in $O(D^{\alpha-1}e)$. I was under the impression that it was $O(D^{\alpha}e)$ i.e. where is the $\alpha-1$ coming from? I'm pretty sure it's trivial, but I'm missing the point. </p>

CC BY-SA 3.0
2015-05-27T09:38:59.860Z
This is a basic mathematic problem. If $x_1\ge x_2\ldots \ge x_n$ then $\Sigma x_i^\alpha \le x_1^{\alpha -1}\Sigma x_i$ for $\alpha \ge 1$.
Saeed
<graph-theory><clique>
Counting the number of K4
BryanS
# Counting the number of K4

(Asked by: username_0 on 2015-05-23)

I was going over this [paper](http://theory.stanford.edu/~virgi/cs267/papers/klokskratschmuller.pdf) and I don't understand a certain proof (section five phase 2).

Given a graph *G=(V,E)* partitioned into the sets of vertices *L* and *H*. The vertices in *L* are at most *D* where *D* is an arbitrary number and the rest of the vertices are in *H*.

If we take a closer look at Phase 2 (Theorem 5). For each vertex *x* in *L* compute the square of the adjacency matrix of *G[N(x)]* to decide whether *G[N(x)]* contains a triangle.

We know that the fastest way to find a triangle in a graph is using fast matrix multiplication algorithm which is $O(n^\alpha)$. So, we can define a running time of $\sum\_{x \epsilon L}^{ } d(x)^\alpha$. Since we know that *|L|* can be at most *e* (number of edges) if we choose a bad *D* and *d(x)* is at most *D*, why Phase 2 can be done in $O(D^{\alpha-1}e)$. I was under the impression that it was $O(D^{\alpha}e)$ i.e. where is the $\alpha-1$ coming from? I'm pretty sure it's trivial, but I'm missing the point.

**Tags:** graph-theory, clique

> **Comments:**
> **username_1**: This is a basic mathematic problem. If $x_1\ge x_2\ldots \ge x_n$ then $\Sigma x_i^\alpha \le x_1^{\alpha -1}\Sigma x_i$ for $\alpha \ge 1$.  

---

## 1 answers

### Answer by username_2 on 2015-05-27. Score: 3 | Accepted answer

The sum of all degrees $d(x)$ in a graph is at most $2e$. The sum of all $d(x)^{\alpha}$ is at most $(max degree)^{\alpha -1}$ times sum of all $d(x)$. Together these give the upper bound.


---

