Encyclopedia

Common graph

Concept in extremal graph theory

Wikipedia contributorsAdapted for Fathomly · View authors

3 min read
Source updated May 26, 2025

In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, $F$ is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of $F$ in any graph $G$ and its complement ${\overline {G}}$ is a large fraction of all possible copies of $F$ on the same vertices. Intuitively, if $G$ contains few copies of $F$ , then its complement ${\overline {G}}$ must contain lots of copies of $F$ in order to compensate for it.

Common graphs are closely related to other graph notions dealing with homomorphism density inequalities. For example, common graphs are a more general case of Sidorenko graphs.

01Definition

A graph $F$ is common if the inequality:

$t(F,W)+t(F,1-W)\geq 2^{-e(F)+1}$

holds for any graphon $W$ , where $e(F)$ is the number of edges of $F$ and $t(F,W)$ is the homomorphism density.

The inequality is tight because the lower bound is always reached when $W$ is the constant graphon $W\equiv 1/2$ .

02Interpretations of definition

For a graph $G$ , we have $t(F,G)=t(F,W_{G})$ and $t(F,{\overline {G}})=t(F,1-W_{G})$ for the associated graphon $W_{G}$ , since graphon associated to the complement ${\overline {G}}$ is $W_{\overline {G}}=1-W_{G}$ . Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means, $W$ to $W_{G}$ , and see $t(F,W)$ as roughly the fraction of labeled copies of graph $F$ in "approximate" graph $G$ . Then, we can assume the quantity $t(F,W)+t(F,1-W)$ is roughly $t(F,G)+t(F,{\overline {G}})$ and interpret the latter as the combined number of copies of $F$ in $G$ and ${\overline {G}}$ . Hence, we see that $t(F,G)+t(F,{\overline {G}})\gtrsim 2^{-e(F)+1}$ holds. This, in turn, means that common graph $F$ commonly appears as subgraph.

In other words, if we think of edges and non-edges as 2-coloring of edges of complete graph on the same vertices, then at least $2^{-e(F)+1}$ fraction of all possible copies of $F$ are monochromatic. Note that in a Erdős-Rényi random graph $G=G(n,p)$ with each edge drawn with probability $p=1/2$ , each graph homomorphism from $F$ to $G$ have probability $2\cdot 2^{-e(F)}=2^{-e(F)+1}$ of being monochromatic. So, common graph $F$ is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph $G$ at the graph $G=G(n,p)$ with $p=1/2$

$p=1/2$ . The above definition using the generalized homomorphism density can be understood in this way.

03Examples

As stated above, all Sidorenko graphs are common graphs. Hence, any known Sidorenko graph is an example of a common graph, and, most notably, cycles of even length are common. However, these are limited examples since all Sidorenko graphs are bipartite graphs while there exist non-bipartite common graphs, as demonstrated below.
The triangle graph $K_{3}$ is one simple example of non-bipartite common graph.
$K_{4}^{-}$ , the graph obtained by removing an edge of the complete graph on 4 vertices $K_{4}$ , is common.
Non-example: It was believed for a time that all graphs are common. However, it turns out that $K_{t}$ is not common for $t\geq 4$ . In particular, $K_{4}$ is not common even though $K_{4}^{-}$ is common.

04Proofs

Sidorenko graphs are common

A graph $F$ is a Sidorenko graph if it satisfies $t(F,W)\geq t(K_{2},W)^{e(F)}$ for all graphons $W$ .

In that case, $t(F,1-W)\geq t(K_{2},1-W)^{e(F)}$ . Furthermore, $t(K_{2},W)+t(K_{2},1-W)=1$ , which follows from the definition of homomorphism density. Combining this with Jensen's inequality for the function $f(x)=x^{e(F)}$ :

$t(F,W)+t(F,1-W)\geq t(K_{2},W)^{e(F)}+t(K_{2},1-W)^{e(F)}\geq 2{\bigg (}{\frac {t(K_{2},W)+t(K_{2},1-W)}{2}}{\bigg )}^{e(F)}=2^{-e(F)+1}$

Thus, the conditions for common graph is met.

The triangle graph is common

Expand the integral expression for $t(K_{3},1-W)$ and take into account the symmetry between the variables:

$\int _{[0,1]^{3}}(1-W(x,y))(1-W(y,z))(1-W(z,x))dxdydz=1-3\int _{[0,1]^{2}}W(x,y)+3\int _{[0,1]^{3}}W(x,y)W(x,z)dxdydz-\int _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz$

Each term in the expression can be written in terms of homomorphism densities of smaller graphs. By the definition of homomorphism densities:

$\int _{[0,1]^{2}}W(x,y)dxdy=t(K_{2},W)$

$\int {[0,1]^{3}}W(x,y)W(x,z)dxdydz=t(K_{1,2},W)$

$\int _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz=t(K_{3},W)$

where $K_{1,2}$ denotes the complete bipartite graph on $1$ vertex on one part and $2$ vertices on the other. It follows:

$t(K_{3},W)+t(K_{3},1-W)=1-3t(K_{2},W)+3t(K_{1,2},W)$ .

$t(K_{1,2},W)$ can be related to $t(K_{2},W)$ thanks to the symmetry between the variables $y$ and $z$ : ${\begin{alignedat}{4}t(K_{1,2},W)&=\int _{[0,1]^{3}}W(x,y)W(x,z)dxdydz&&\\&=\int _{x\in [0,1]}{\bigg (}\int _{y\in [0,1]}W(x,y){\bigg )}{\bigg (}\int _{z\in [0,1]}W(x,z){\bigg )}&&\\&=\int _{x\in [0,1]}{\bigg (}\int _{y\in [0,1]}W(x,y){\bigg )}^{2}&&\\&\geq {\bigg (}\int _{x\in [0,1]}\int _{y\in [0,1]}W(x,y){\bigg )}^{2}=t(K_{2},W)^{2}\end{alignedat}}$

where the last step follows from the integral Cauchy-Schwarz inequality. Finally:

$t(K_{3},W)+t(K_{3},1-W)\geq 1-3t(K_{2},W)+3t(K_{2},W)^{2}=1/4+3{\big (}t(K_{2},W)-1/2{\big )}^{2}\geq 1/4$ .

This proof can be obtained from taking the continuous analog of Theorem 1 in "On Sets Of Acquaintances And Strangers At Any Party"

Watch videos about Common graphExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Common graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.