# Counting the number of K4

I was going over this paper 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.

• 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 May 27 '15 at 9:38

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.