1
$\begingroup$

Determine the highest possible number of edges in a planar graph, which does not contain C3 or C4 (C = cycle, 3,4 = length of the cycle).

Details: you are given $n$ vertices and they are asking you the highest possible number of edges in a planar graph with the $n$ vertices, while satisfying the condition of not containing $C_3$ or $C_4$. Sorry if I was unclear, english is not my main language.

$\endgroup$
  • $\begingroup$ @achillehui you are given $n$ vertices and they are asking you the highest highest possible number of edges in a planar graph with $n$ vertices, while satisfying the condition of not containing $C_3$ or $C_4$. Sorry if I was unclear, english is not my main language. $\endgroup$ – Mykybo Jan 11 '16 at 21:09
  • $\begingroup$ @Mykybo, well, what exactly do you mean by «not containing $C_3$ or $C_4$»? $\endgroup$ – Mariano Suárez-Álvarez Jan 11 '16 at 22:32
  • $\begingroup$ @MarianoSuárez-Alvarez not containing $C_3$ or $C_4$ basicly means there won't be a subgraph in shape of triangle or square.. $\endgroup$ – Mykybo Jan 11 '16 at 22:46
3
+50
$\begingroup$

I will assume we are talking about simple graphs, i.e

  • there are no edge that join a vertex with itself.
  • between any two vertices, there is at most one edge joining them.

Otherwise, it is trivial to construct graph with $n$ vertices and arbitrary large number of edges.

Let $e$ be the number of edges of the graph.

Since the graph is planar, we can put in on the surface of a sphere. We start to remove dangling vertices, i.e vertices which connect to either $0$ or $1$ edge, from the graph. At the end, there are two possibilities:

Case I - the graph reduces to a single dangling vertex.

The original graph is a forest of trees and isolated vertices. The total number of edges $e$ is at most $n-1$.

Case II - the graph reduces to one composed of closed loops.

Let $V, E, F$ and $C$ be the number of vertices, edges, faces (on sphere) and connected components of remaining graph. It is clear $C \ge 1$, $V \ge 3C$ and we have removed $e-E \le n-V$ edges from the original graph. Let $F_k$ be the number of faces with $k$ sides. We have

  • $F_1 = F_2 = 0$ because the graph is simple.
  • $F_3 = F_4 = 0$ because we assume the graph doesn't contain $C_3$ nor $C_4$ as a subgraph.

This leads to $$2E = \sum_{k=5}^\infty k F_k \ge 5 \sum_{k=5}^\infty F_k = 5F$$

Since $V - E + F = 1+C$, we find: $$V - (1+C) = E - F \ge \frac32 F \quad\implies\quad F \le \frac23 (V-(1+C))$$ As a result, $$E = V + F - (1+C) \le \frac53 (V-(1+C)) \le \frac53 (V-2)$$

Adding back the $e - E$ edges we have removed before, we get:

$$e = (e-E) + E \le (n-V) + \frac53 (V-2) \le \frac53(n-2)$$

Combining estimates of these two cases, we can conclude

$$e \le \mathcal{N}(n) \stackrel{def}{=} \max\left(n-1, \left\lfloor\frac53(n-2)\right\rfloor \right) = \begin{cases} n - 1, & n \le 4,\\ \left\lfloor\frac53(n-2)\right\rfloor, & n > 5 \end{cases} $$

It turns out this upper bound $\mathcal{N}$ is optimal.

  • For $n = 1,\ldots, 4$, the result is obvious.
  • For $n = 5$ and $6$, the pentagon and hexagon has $\mathcal{N}(n) = n$ edges and fit the requirement.
  • For $n = 7$, start from a hexagon, add one vertex and two edges inside to split the hexagon to obtain a graph of two pentagons with $\mathcal{N}(7) = 8$ edges ( left figure at picture below ).

$\hspace1.5in$ A tale of two pentagons

  • For $n = 5+3k$ or $7+3k$ where $k > 0$, we can use the fact start from a pentagon, we can add three vertices and five edges inside to split it into $3$ pentagons (right figure at picture above). This allow one to reduce the case from $n$ to $n-3$ vertices.

  • For $n = 6+3k$ where $k > 0$, we can start from the graph for $5+3k$ constructed above, split one edge by adding a vertex.

$\endgroup$
  • $\begingroup$ shouldn't $n_k$ be the number of vertices with k edges, and not number of faces? $\endgroup$ – Mykybo Jan 12 '16 at 8:55
  • $\begingroup$ $n_k$ are number of faces with $k$ sides. To avoid confusion, I changed all of them from $n_k$ to $F_k$. In any event, start from the absense of $C_3$ and $C_4$, there is no obvious constraint on the number of vertices with $k$ edges. $\endgroup$ – achille hui Jan 12 '16 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.