Is the number of maximal cliques of a planar graph bounded by its number of faces?

110 Views Asked by At

I would like to know if there is any relationship between the number of maximal cliques in a planar graph, and its number of faces?

It is known that for a planar graph $G$, if $H\subseteq G$ is a clique of $G$ then $|H|\leq 4$.

It is also known that the number of faces $f$ of $G$ is given by $f\leq 2v-4$.

Let $m$ be the number of maximal cliques of $G$.

Does it follow from the above that $m\leq 2v-4$?

Is there a more precise quantity that describes the number of maximal cliques of a planar graph?

1

There are 1 best solutions below

4
On BEST ANSWER

If we forget about maximality for the moment, then in an $n$-vertex planar graph where $n \ge 3$, the following bounds hold.

Fact 1. The number of $2$-cliques is at most $3n-6$.

Proof. This is just the usual upper bound on the number of edges in a planar graph.

Fact 2. The number of $3$-cliques is at most $3n-8$.

We induct on $n$. For $n=3$, there is at most $1$ clique, and $1 = 3\cdot 3 -8$.

For $n \ge 4$, if our graph has no $3$-cliques that are not faces, then we're done: there are at most $2n-4$ faces, so the number of $3$-cliques is also at most $2n-4 \le 3n-8$. If there is a $3$-clique $C$ that is not a face, then we split up $G$ into two graphs $G'$ and $G''$, formed by deleting the interior of $C$ (in some fixed plane embedding) and the exterior of $C$, respectively. These have $n'$ and $n''$ vertices where $3 \le n', n'' < n$ and $n' + n'' = n+3$; every $3$-clique of $G$ is in either $G'$ or $G''$, but $C$ is counted twice. By induction, there are at most $(3n'-8)+(3n''-8)-1$ cliques in $G$, which is $3(n+3) - 17 = 3n-8$.

Fact 3. The number of $4$-cliques is at most $n-3$.

We induct on $n$ again. For $n=3$, we should get $0$, and for $n=4$, we should get $1$.

For $n \ge 5$, suppose our graph $G$ contains a $4$-clique on vertices $\{v_1, v_2, v_3, v_4\}$. We will take four graphs $G_1, G_2, G_3, G_4$ obtained as follows (with respect to a fixed plane embedding of $G$): in $G_1$ we delete everything on the same side (interior or exterior) of the cycle $v_2 v_3 v_4$ as $v_1$, and do the corresponding thing for $G_2, G_3, G_4$. Let these graphs have $n_1, n_2, n_3, n_4$ vertices. Then $$(n_1 - 3) + (n_2 - 3) + (n_3 - 3) + (n_4 - 3) = n-4$$ because both sides count the vertices in $G$ other than $\{v_1, v_2, v_3, v_4\}$, so $n_1 + n_2 + n_3 + n_4 =n+8$. Every $4$-clique in $G$ except the one we found is contained in some $G_i$, and each $G_i$ contains between $3$ and $n-1$ vertices, so by induction the number of cliques in $G$ is at most $$(n_1-3) + (n_2 -3) + (n_3 - 3) + (n_4 - 3) + 1$$ which simplifies to $(n+8)-12 + 1$ or $n-3$.


From these facts, we get a weak upper bound on the number of maximal cliques: $$(3n-6) + (3n-8) + (n-3) = 7n-17.$$ This is just a bound on the number of $2$-cliques, $3$-cliques, and $4$-cliques, whether or not they're maximal.

Both Fact 2 and Fact 3 are tight for Apollonian networks, but in Apollonian networks, none of the $3$-cliques are maximal, so those have an unusually low number of maximal cliques.