6
$\begingroup$

Let $f(G)$ denote the number of $K_4$ in a graph $G$ and $e(G)$ denote the number of edges of $G$.

Consider two simple graphs $G_1$ and $G_2$ having the same set $V$ of $n$ vertices and let $H_1(U)$ and $H_2(U)$ be subgraphs of $G_1$ and $G_2$, respectively, having the same set $U$ of vertices.

If $M= {\max } |e(H_{1}(U))-e(H_{2}(U))|$, over all ${U \subseteq V, H_1 \subseteq G_1, H_2 \subseteq G_2}$, is it true that:

$|f(G_{1})-f(G_{2})| \leq Mn^2$?

I am looking for a proof or reference for the previous problem. Any suggestion would be appreciated.
Thanks in advance.

Improve this question
$\endgroup$
5
  • $\begingroup$ Are the subgraphs in your definition induced? $\endgroup$
    – Moritz
    Commented Aug 20, 2016 at 16:13
  • $\begingroup$ @Moritz Yes, the subgraphs are induced. $\endgroup$
    – jack
    Commented Aug 20, 2016 at 20:44
  • 1
    $\begingroup$ If I'm reading the definitions correctly then $G_1$ and $G_2$ differ in at most $M$ edges. Each edge is contained in less that $n^2/2$ $K_4$'s, so the inequality is immediate. $\endgroup$
    – Ben Barber
    Commented Aug 29, 2016 at 11:57
  • $\begingroup$ @BenBarber Thank you! It was simpler than I thought. $\endgroup$
    – jack
    Commented Aug 31, 2016 at 20:58
  • $\begingroup$ @BenBarber Can you repost your comment as an answer so that the question can be closed? $\endgroup$
    – D. Ror.
    Commented Oct 21, 2016 at 20:14

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .