<p>I think the answer to your first question is "no".</p>

<p>In particular, if you take a random bipartite graph $G=([n],[n],E)$
where $Pr[(i,j)\in E] = 1/2$ for each pair $(i,j)$,
the answer is no with probability close to 1.</p>

<p>I am interpreting your first question as follow:</p>

<p>Given any graph $G$, is it <em>always</em> possible to find a collection of subgraphs such that </p>

<ul>
<li>each subgraph is a complete $k$-partite graph for some $k$,</li>
<li>each edge in $G$ occurs in at least one of the subgraphs, and</li>
<li>each vertex in $G$ occurs in at most a constant number of the subgraphs?</li>
</ul>

<p><em>Proof.</em>
Fix $n$.  Let $G$ be the random graph described above.</p>

<p>Since $G$ is bipartite any complete $k$-partite subgraph has to be bipartite.</p>

<p>First, I claim that with probability $1-o(1)$, every complete bipartite subgraph of $G$ has at most $4n$ edges.  </p>

<p>(Here's why.
For any pair of subsets $L\subseteq [n]$ and $R\subseteq [n]$ with $|L\times R| \ge 4n$,
the probability that the complete bipartite subgraph with edge set $L\times R$
is in $G$ is $2^{-|L\times R|} \le 2^{-4n}$.
There are fewer than $2^n\times 2^n = 4^n$ such pairs $L$ and $R$,
Thus, by the naive union bound, the probability that any of
the corresponding subgraphs is present in $G$ is at most $4^n 2^{-4n} \le 2^{-2n}$.)</p>

<p>Also, with probability $1-o(1)$, the graph $G$ has at least $n^2/4$ edges.</p>

<p>Thus, with probability $1-o(1)$, every complete bipartite subgraph in $G$
has at most $4n$ edges, and $G$ has at least $n^2/4$ edges.
Assume this happens.  </p>

<p>Now suppose for contradiction that a collection of subgraphs with the desired properties exists.
Each of the subgraphs has edge set $L\times R$ for some pair of subsets $L$ and $R$.
In $G$, <em>direct</em> all the edges in $L\times R$ from the larger side to the smaller side
(to the left if $|L|\le |R|$, and to the right otherwise).
Since $|L\times R|\le 4n$, the smaller of $L$ or $R$ must have size at most $2\sqrt n$.</p>

<p>Since each vertex is in $O(1)$ of the subgraphs, each vertex now has $O(\sqrt n)$
edges directed out of it.  But all edges are directed one way or the other,
so the number of edges in $G$ is at most the number of vertices 
times the maximum out-degree of any vertex, that is, at most $O(n\sqrt n)$.
This contradicts the graph having at least $n^2/4$ edges.</p>

CC BY-SA 3.0
2012-11-22T21:32:10.710Z
2012-11-22T21:32:10.710Z
Neal Young
<p>Given an undirected graph $G$ with $n$ vertice and $m$ edges, can we construct $p$ <strong>complete $k_i$-partite graphs</strong>, where $p$ is finite (of course) and <strong>each vertex appears at most a constant number of times</strong>, satifying " the sum of such $p$ complete $k_i$-partite graphs is $G$ " ?  Moreover, such construction can be done in <em>poly-time</em> ?</p>

<graph-theory><co.combinatorics><graph-algorithms>
Any graph $G$ can be seen as the sum of complete $k_i$-partite graphs?
Micheal
# Any graph $G$ can be seen as the sum of complete $k_i$-partite graphs?

(Asked by: username_0 on 2012-11-22)

Given an undirected graph $G$ with $n$ vertice and $m$ edges, can we construct $p$ **complete $k\_i$-partite graphs**, where $p$ is finite (of course) and **each vertex appears at most a constant number of times**, satifying " the sum of such $p$ complete $k\_i$-partite graphs is $G$ " ? Moreover, such construction can be done in *poly-time* ?

**Tags:** graph-theory, co.combinatorics, graph-algorithms

---

## 1 answers

### Answer by username_1 on 2012-11-22. Score: 8 | Accepted answer

I think the answer to your first question is "no".

In particular, if you take a random bipartite graph $G=([n],[n],E)$
where $Pr[(i,j)\in E] = 1/2$ for each pair $(i,j)$,
the answer is no with probability close to 1.

I am interpreting your first question as follow:

Given any graph $G$, is it *always* possible to find a collection of subgraphs such that

* each subgraph is a complete $k$-partite graph for some $k$,
* each edge in $G$ occurs in at least one of the subgraphs, and
* each vertex in $G$ occurs in at most a constant number of the subgraphs?

*Proof.*
Fix $n$. Let $G$ be the random graph described above.

Since $G$ is bipartite any complete $k$-partite subgraph has to be bipartite.

First, I claim that with probability $1-o(1)$, every complete bipartite subgraph of $G$ has at most $4n$ edges.

(Here's why.
For any pair of subsets $L\subseteq [n]$ and $R\subseteq [n]$ with $|L\times R| \ge 4n$,
the probability that the complete bipartite subgraph with edge set $L\times R$
is in $G$ is $2^{-|L\times R|} \le 2^{-4n}$.
There are fewer than $2^n\times 2^n = 4^n$ such pairs $L$ and $R$,
Thus, by the naive union bound, the probability that any of
the corresponding subgraphs is present in $G$ is at most $4^n 2^{-4n} \le 2^{-2n}$.)

Also, with probability $1-o(1)$, the graph $G$ has at least $n^2/4$ edges.

Thus, with probability $1-o(1)$, every complete bipartite subgraph in $G$
has at most $4n$ edges, and $G$ has at least $n^2/4$ edges.
Assume this happens.

Now suppose for contradiction that a collection of subgraphs with the desired properties exists.
Each of the subgraphs has edge set $L\times R$ for some pair of subsets $L$ and $R$.
In $G$, *direct* all the edges in $L\times R$ from the larger side to the smaller side
(to the left if $|L|\le |R|$, and to the right otherwise).
Since $|L\times R|\le 4n$, the smaller of $L$ or $R$ must have size at most $2\sqrt n$.

Since each vertex is in $O(1)$ of the subgraphs, each vertex now has $O(\sqrt n)$
edges directed out of it. But all edges are directed one way or the other,
so the number of edges in $G$ is at most the number of vertices
times the maximum out-degree of any vertex, that is, at most $O(n\sqrt n)$.
This contradicts the graph having at least $n^2/4$ edges.


---

