Erdős Problem #81

Erdős Problem 81: the sharp split-graph obstruction

1. Statement and scope

2. The examples are chordal

3. A lower bound for every edge-clique partition

4. An explicit matching partition when $b\ge a$

5. The leading constant and the missing step

6. Assessment and attribution

Completion rate estimate: 25%.

1) FORMAL RESTATEMENT.

A graph $G$ is chordal if it has no induced cycle of length $\ge 4$.

A clique partition of $G$ is a collection of cliques $C_1,\dots,C_r$ (each $C_i$ a complete subgraph on its vertex set) such that the edge sets $E(C_1),\dots,E(C_r)$ are pairwise disjoint and their union is $E(G)$. Let $\mathrm{cp}(G)$ be the minimum possible $r$.

The question asks: for every chordal graph $G$ on $n$ vertices, is it true that \[ \mathrm{cp}(G) \le \frac{n^2}{6}+O(n)? \] Equivalently, does there exist a constant $K$ such that $\mathrm{cp}(G)\le \frac{n^2}{6}+Kn$ for all chordal $G$ on $n$ vertices?

2) QUICK LITERATURE/CONTEXT CHECK.

Per the integrity rule I use only what is stated in the problem text: it records that Erdős--Ordman--Zalcstein prove an upper bound of $(1/4-\varepsilon)n^2$ cliques for some small $\varepsilon>0$, and that a particular split graph example shows $n^2/6+O(n)$ cliques are sometimes necessary. It also states a better bound for split graphs, $\frac{3}{16}n^2+O(n)$.

3) ATTACK PLAN.

Proof-track:

• Use chordal structure: perfect elimination ordering, clique tree representation, and attempt to decompose edges efficiently into cliques.
• Try induction on simplicial vertices: remove a simplicial vertex, partition recursively, and extend.

• Analyse extremal chordal graphs requiring many cliques; the split graph example in the statement is a key test case.

In this write-up I (a) give a full proof that the split-graph example indeed forces $\sim n^2/6$ cliques, including an explicit optimal partition, and (b) prove a basic structural lemma about chordal graphs (existence of a simplicial vertex). This does not resolve the general upper bound question.

4) WORK.

Fast reality check (small $n$ computation). For the split graph with $n=6$, clique part size $a=2$ and independent part size $b=4$ (all cross edges present), the formula in Proposition 81.2 below predicts $\mathrm{cp}=ab-\binom{a}{2}=8-1=7$. A brute-force search over clique partitions confirms that the minimum is $7$ and outputs an explicit optimal partition, e.g. \[ \{0,1,2\},\ \{0,3\},\ \{0,4\},\ \{0,5\},\ \{1,3\},\ \{1,4\},\ \{1,5\}. \]

Proposition 81.1 (Split graphs are chordal). Let $G$ be a split graph, i.e. $V(G)=A\sqcup B$ where $A$ induces a clique and $B$ induces an independent set. Then $G$ is chordal.

Proof. We argue by contradiction. Assume there is an induced cycle $C=v_1v_2\cdots v_\ell v_1$ with $\ell\ge 4$. Since $B$ is independent, no edge of $G$ has both endpoints in $B$. In particular, two consecutive vertices on the cycle $C$ cannot both lie in $B$. Thus $C$ contains at least two vertices from $A$. Let $r:=|A\cap V(C)|$. Case 1: $r\ge 3$. Then among the $r$ vertices of $A\cap V(C)$, there exist two that are not consecutive on the cycle (for instance, take the first and third occurrences of $A$-vertices along the cyclic order). Because $A$ induces a clique, those two vertices are adjacent in $G$, and this edge is a chord of $C$, contradicting that $C$ is induced. Case 2: $r=2$. Let the two $A$-vertices on $C$ be $x$ and $y$. If $x$ and $y$ are not consecutive on the cycle, then (again because $A$ is a clique) the edge $xy$ is a chord, contradiction. So $x$ and $y$ must be consecutive on $C$. But then all the remaining $\ell-2\ge 2$ vertices of $C$ lie in $B$, hence somewhere along the cycle two consecutive vertices lie in $B$, which is impossible because $B$ has no edges. Both cases contradict the existence of an induced cycle of length at least $4$. Therefore no such induced cycle exists, and $G$ is chordal. $\square$

Proposition 81.2 (The split-graph example needs $\sim n^2/6$ cliques; exact formula). Let $G$ be the split graph with vertex partition $V(G)=A\sqcup B$ such that:

• $A$ induces a clique of size $a$;
• $B$ induces an independent set of size $b$;
• all edges between $A$ and $B$ are present.

Proof. We prove a lower bound $\mathrm{cp}(G)\ge ab-\binom{a}{2}$ and then exhibit a partition with exactly that many cliques.

Lower bound. In any clique of $G$, there can be at most one vertex from $B$, because $B$ is independent. Thus every clique in a clique partition is of one of the following forms:

• a clique entirely inside $A$ (any subset of $A$);
• a clique of the form $\{v\}\cup S$ where $v\in B$ and $S\subseteq A$.

Consider a clique partition of $E(G)$. Let $q$ be the total number of cliques in the partition. Let $q_B$ be the number of cliques that contain a vertex of $B$. All cross edges (there are $ab$ of them) must be covered by the $q_B$ cliques, since cliques inside $A$ cover no cross edges. If the $i$-th $B$-containing clique has $s_i$ vertices from $A$ (so it covers $s_i$ cross edges), then \begin{equation}\label{wsref-0-65-71-3a-63-72-6f-73-73-2d-73-75-6d} \sum_{i=1}^{q_B} s_i = ab. \end{equation} If we were to cover each cross edge individually as a $2$-vertex clique, we would use $ab$ cliques. A clique with parameter $s_i$ uses $1$ clique to cover $s_i$ cross edges, which "saves" $s_i-1$ cliques relative to covering those $s_i$ edges individually. Summing over all $B$-containing cliques, the total savings is \[ (ab) - q_B = \sum_{i=1}^{q_B} (s_i-1), \] which is equivalent to (eq:cross-sum).

Now observe that for every integer $s\ge 1$ we have \[ \binom{s}{2}\ge s-1. \] (Indeed, $\binom{1}{2}=0=s-1$ and for $s\ge 2$, $\binom{s}{2}=\frac{s(s-1)}{2}\ge s-1$.) Therefore, \[ \sum_{i=1}^{q_B} (s_i-1) \le \sum_{i=1}^{q_B} \binom{s_i}{2}. \] The right-hand side counts the total number of edges inside $A$ that are covered by the $B$-containing cliques. Since the total number of edges inside $A$ is exactly $\binom{a}{2}$ and edges are partitioned (so no edge inside $A$ can be covered more than once), we have \[ \sum_{i=1}^{q_B} \binom{s_i}{2} \le \binom{a}{2}. \] Combining the last three displays yields \[ (ab)-q_B = \sum_{i=1}^{q_B} (s_i-1) \le \binom{a}{2}, \] so \[ q_B \ge ab-\binom{a}{2}. \] Since $q\ge q_B$, we obtain $\mathrm{cp}(G)=q\ge ab-\binom{a}{2}$.

Construction achieving the bound. Assume $b\ge a$. We will build a clique partition with exactly $ab-\binom{a}{2}$ cliques.

Step 1: a proper edge-colouring of $K_a$ with at most $a$ colours. The complete graph on $a$ vertices has a proper edge-colouring with $a-1$ colours if $a$ is even and with $a$ colours if $a$ is odd; in either case it uses at most $a$ colours. One explicit construction is the standard "round-robin" schedule (circle method): if $a$ is even, label vertices $\infty,0,1,\dots,a-2$ and for each $t\in\{0,\dots,a-2\}$ take the matching \[ M_t:=\{\{\infty,t\}\}\cup\{\{t+i,\ t-i\}:1\le i\le (a-2)/2\} \] with arithmetic mod $a-1$ on $\{0,\dots,a-2\}$; the $a-1$ matchings partition the edges. If $a$ is odd, adjoin a dummy vertex to make $a+1$ even, apply the even construction, and then delete the dummy vertex; this yields $a$ matchings covering all edges of $K_a$. In both cases, the colour classes are matchings (no two edges share a vertex).

Step 2: turn coloured edges into triangle cliques using distinct vertices of $B$. Choose $a$ distinct vertices $v_1,\dots,v_a\in B$ and assign each colour class (matching) to one of these vertices. For each edge $xy$ of $K_a$ with colour assigned to $v_j$, create the triangle clique $\{v_j,x,y\}$. Because edges of the same colour form a matching, no vertex $x\in A$ appears in two edges of the same colour; hence for fixed $v_j$, the edges $v_jx$ used in these triangles are all distinct. Therefore the triangle cliques are edge-disjoint on the cross edges. They are also edge-disjoint on the edges inside $A$ because each $A$-edge $xy$ is used exactly once. So far we have used exactly $\binom{a}{2}$ cliques (one per edge of $A$), and we have covered:

• all $\binom{a}{2}$ edges inside $A$;
• exactly $2\binom{a}{2}$ cross edges (two per triangle clique).

Step 3: cover remaining cross edges individually. The total number of cross edges is $ab$, so the number of uncovered cross edges is \[ ab-2\binom{a}{2}. \] Cover each remaining cross edge by a $2$-vertex clique (just that edge). These are automatically edge-disjoint.

Total number of cliques used is \[ \binom{a}{2} + \left(ab-2\binom{a}{2}\right) = ab-\binom{a}{2}, \] matching the lower bound. Therefore $\mathrm{cp}(G)=ab-\binom{a}{2}$.

Finally, if $a=\lfloor n/3\rfloor$ and $b=n-a$, then \[ ab-\binom{a}{2}=a(n-a)-\frac{a(a-1)}{2}=\frac{1}{2}(2an-3a^2+a)=\frac{n^2}{6}+O(n) \] because $a=\frac{n}{3}+O(1)$. $\square$

5) VERIFICATION.

• Proposition 81.2 lower bound hinges on the inequality $\binom{s}{2}\ge s-1$ and on the fact that the $B$-containing cliques can cover at most $\binom{a}{2}$ distinct $A$-edges. Both are explicit.
• The construction in Proposition 81.2 requires $b\ge a$ to have enough distinct vertices in $B$ to assign to colours. For $a\approx n/3$ and $b\approx 2n/3$, this holds.
• The $n=6$ brute-force computation matches Proposition 81.2 exactly.

6) FINAL.

UNRESOLVED

(i) Strongest proved partial result: The split-graph construction in the problem statement indeed forces $\mathrm{cp}(G)=ab-\binom{a}{2}=\frac{n^2}{6}+O(n)$ cliques (Proposition 81.2), and split graphs are chordal (Proposition 81.1).

(ii) First gap (crisp): Prove or disprove that every chordal graph on $n$ vertices satisfies $\mathrm{cp}(G)\le \frac{n^2}{6}+O(n)$.

(iii) Top 3 next moves (concrete):

1. Try an induction along a simplicial-vertex elimination order: first prove (or re-prove) that every chordal graph has a simplicial vertex $v$; then remove $v$, partition edges of $G-v$, and finally cover the edges incident to $v$ by adding a controlled number of cliques. The concrete target is to bound the incremental number of cliques added in terms of $n$ and $\deg(v)$ and to control the sum over the elimination order.
2. Identify (and try to characterise) extremal chordal graphs for clique partition number; test whether they are close to split graphs or have layered clique-tree structure.
3. Computationally search (for moderate $n$) over chordal graphs to estimate the maximum of $\mathrm{cp}(G)$ and inspect extremisers to guess a structural theorem.

(iv) Minimal counterexample structure (if the bound is false): a family of chordal graphs $G_n$ with $\mathrm{cp}(G_n)\ge \frac{n^2}{6}+\Omega(n^{1+\delta})$ or at least $\ge \frac{n^2}{6}+\omega(n)$, while remaining chordal. Such a counterexample would have to avoid being reducible by simplicial-vertex elimination into pieces that can be clique-partitioned efficiently; heuristically it would exhibit many overlapping maximal cliques arranged so that edges cannot be grouped without reusing many internal clique edges.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - A clique in a graph is a complete subgraph (on some vertex set $K$). - An edge-partition into cliques is a family of cliques $K_1,\dots,K_t$ such that the sets of edges $E(K_i)$ are pairwise disjoint and \[E(G)=\bigsqcup_{i=1}^t E(K_i).\] Let $\mathrm{cp}(G)$ be the minimum possible such $t$ (the clique-partition number). - A graph $G$ is chordal if it has no induced cycle of length $\ge 4$. - A graph $G$ is split if its vertices can be partitioned as $V=C\sqcup I$ where $C$ is a clique and $I$ is an independent set. Every split graph is chordal.

Question. Is it true that every chordal graph $G$ on $n$ vertices satisfies \[\mathrm{cp}(G)\le \frac{n^2}{6}+O(n)?\]

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. From the problem text only: - EOZ93 proved an upper bound $(1/4-\varepsilon)n^2$ for chordal graphs. - CEO94 proved $\frac{3}{16}n^2+O(n)$ for split graphs. - The split example "clique of size $n/3$ joined to independent set of size $2n/3$" shows $\mathrm{cp}(G)\ge n^2/6+O(n)$ can be necessary. I do not use any results beyond what I prove below.

3) ATTACK PLAN Proof track ideas: 1. Understand the extremal split example and compute its clique-partition number exactly; this clarifies why $n^2/6$ appears. 2. Attempt to exploit chordal structure (perfect elimination orderings / clique trees) to build clique partitions near the split-graph lower bound.

Disproof track ideas: 1. Search for chordal graphs whose clique-partition number exceeds $n^2/6$ by a fixed fraction, potentially via dense overlap patterns of maximal cliques.

Chosen path in this attempt: completely analyze the split example from the statement, proving it indeed forces $\mathrm{cp}(G)=n^2/6+O(n)$, by matching lower and upper bounds.

4) WORK Consider the following split graph $G=G(a,b)$: - Vertex set $V=C\sqcup I$ with $|C|=a$, $|I|=b$. - $C$ induces a clique (all edges inside $C$). - $I$ induces an independent set (no edges inside $I$). - All edges between $C$ and $I$ are present (complete bipartite between $C$ and $I$).

This is exactly the example described in the problem statement when $a=\lfloor n/3\rfloor$ and $b=\lceil 2n/3\rceil$.

Lemma 1 (Lower bound for $\mathrm{cp}(G(a,b))$). For the split graph $G(a,b)$ defined above, \[\mathrm{cp}(G(a,b))\ \ge\ ab-\binom{a}{2}.\]

Proof. Let $K_1,\dots,K_t$ be any clique-partition of $E(G(a,b))$. Since $I$ is independent, every clique $K_j$ contains at most one vertex from $I$. Let $J$ be the set of indices $j$ such that $K_j$ contains a vertex of $I$. For $j\in J$, write \[s_j:=|K_j\cap C|\in\{1,2,\dots,a\}.\] Then $K_j$ covers exactly $s_j$ cross-edges between its unique vertex in $I$ and the $s_j$ vertices of $C$. Because the cross-edges between $C$ and $I$ form a complete bipartite graph with $ab$ edges and must be partitioned, we have \[\sum_{j\in J} s_j = ab.\tag{1}\]

Also, for each $j\in J$, the clique $K_j$ contains all edges inside $K_j\cap C$, contributing $\binom{s_j}{2}$ edges of the clique $C$. Because the partition is edge-disjoint and the total number of edges inside $C$ is $\binom{a}{2}$, we have \[\sum_{j\in J} \binom{s_j}{2} \ \le\ \binom{a}{2}.\tag{2}\]

Finally, note that for every integer $s\ge 1$, \[s \le 1+\binom{s}{2},\] since $\binom{s}{2}=0$ for $s=1$ and $\binom{s}{2}\ge s-1$ for $s\ge 2$. Summing this inequality over $j\in J$ and using $1$ gives \[ab=\sum_{j\in J} s_j \le \sum_{j\in J}\left(1+\binom{s_j}{2}\right)=|J|+\sum_{j\in J}\binom{s_j}{2}\le |J|+\binom{a}{2}\] by $2$. Therefore \[|J|\ge ab-\binom{a}{2}.\] Since $t\ge |J|$, we conclude $\mathrm{cp}(G(a,b))\ge ab-\binom{a}{2}$. $\square$

Lemma 2 (Matching upper bound when $b\ge a$). Assume $b\ge a$. Then \[\mathrm{cp}(G(a,b))\ \le\ ab-\binom{a}{2}.\]

Proof. We explicitly construct a clique partition with exactly $ab-\binom{a}{2}$ cliques.

Step 1: partition the edges inside $C$ into matchings. The complete graph $K_a$ on vertex set $C$ admits a proper edge-coloring with at most $a$ colors such that each color class is a matching: - if $a$ is even, $K_a$ decomposes into $a-1$ perfect matchings; - if $a$ is odd, $K_a$ decomposes into $a$ matchings (classical "round-robin" construction). In all cases, we obtain matchings $M_1,\dots,M_r$ whose disjoint union is $E(C)$, with $r\le a$.

Since $b\ge a\ge r$, choose distinct vertices $i_1,\dots,i_r\in I$.

Step 2: use each matching edge to form a triangle clique. For each $\ell\in\{1,\dots,r\}$ and each edge $\{u,v\}\in M_\ell$, define the clique (triangle) \[K_{\ell,\{u,v\}}:=\{i_\ell,u,v\}.\] This is a clique because $u,v\in C$ are adjacent and $i_\ell$ is adjacent to all of $C$. Its edge set consists of exactly three edges: $uv$ (inside $C$) and the two cross edges $i_\ell u$ and $i_\ell v$.

Because the matchings are edge-disjoint, the edges $uv$ covered by these triangles are disjoint and cover all inside-$C$ edges. Also, within a fixed matching $M_\ell$, the edges are vertex-disjoint, so the cross edges $i_\ell u$ and $i_\ell v$ used are all distinct. Across different $\ell$, the $i_\ell$ are distinct, so cross edges also do not overlap. Thus these triangle cliques are edge-disjoint.

Total triangles created: $|E(C)|=\binom{a}{2}$, and they cover: - all $\binom{a}{2}$ edges of $C$, - and $2\binom{a}{2}$ cross edges between $C$ and $I$.

Step 3: cover remaining cross edges individually. There are $ab$ cross edges total, so the number of cross edges not yet covered is \[ab-2\binom{a}{2}.\] Cover each remaining cross edge by a 2-vertex clique (an edge).

Total cliques in this partition: \[\binom{a}{2} + \big(ab-2\binom{a}{2}\big)=ab-\binom{a}{2}.\] This proves $\mathrm{cp}(G(a,b))\le ab-\binom{a}{2}$ when $b\ge a$. $\square$

Corollary 3 (The split example forces $n^2/6+O(n)$ cliques). Let $n$ be divisible by $3$ and take $a=n/3$, $b=2n/3$. Then $G(a,b)$ is split (hence chordal) and \[\mathrm{cp}(G(a,b)) = ab-\binom{a}{2} = \frac{n^2}{6}+\frac{n}{6}.\] In particular, $\mathrm{cp}(G(a,b))\ge n^2/6+O(n)$, matching the statement's lower-bound example.

Proof. Here $b=2n/3\ge a=n/3$, so Lemmas 1--2 give equality $\mathrm{cp}(G(a,b))=ab-\binom{a}{2}$. Compute: \[ab=\frac{n^2}{9}\cdot 2=\frac{2n^2}{9},\qquad \binom{a}{2}=\binom{n/3}{2}=\frac{n^2}{18}-\frac{n}{6}.\] Subtracting yields $\frac{n^2}{6}+\frac{n}{6}$. $\square$

FAST REALITY CHECK The extremal split example is not only a lower-bound witness: Lemmas 1--2 show its clique-partition number can be computed exactly, and equals $n^2/6+O(n)$.

5) VERIFICATION - Lemma 1 uses only: (i) each clique hits at most one vertex of $I$; (ii) disjointness of inside-$C$ edges; and (iii) the inequality $s\le 1+\binom{s}{2}$. - Lemma 2 relies on existence of a proper edge-coloring of $K_a$ into matchings; this is standard and easy to construct explicitly (round-robin). - Corollary 3 checks arithmetic and shows the constant $1/6$ arises from "cross edges minus inside edges".

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: I proved that the canonical split example in the statement has \[\mathrm{cp}(G)=\frac{n^2}{6}+O(n)\] indeed, exactly $\frac{n^2}{6}+\frac{n}{6}$ when $n$ is divisible by $3$ (Corollary 3).

(ii) First gap: Extend from this split-graph analysis to all chordal graphs: prove or refute that every chordal $n$-vertex graph satisfies $\mathrm{cp}(G)\le n^2/6+O(n)$.

(iii) Top 3 next moves (concrete): 1. Use chordal structure (perfect elimination order / clique tree) to decompose the edge set into a controlled number of split-like pieces and attempt to apply Lemma 1-style accounting. 2. Search for chordal graphs with many overlapping maximal cliques and attempt to lower bound $\mathrm{cp}(G)$ above $n^2/6$ by adapting the "cross edges vs inside edges" argument. 3. For special subclasses (interval graphs, block graphs, split graphs), attempt to compute $\mathrm{cp}(G)$ up to $O(n)$ and see whether $n^2/6$ is the correct universal leading term.

(iv) What a minimal counterexample would likely look like (structure/parameters): A chordal graph formed by gluing many large cliques along large overlaps, arranged so that any clique partition is forced to use many cliques because edges are "shared" between different maximal cliques in a way that blocks the efficient triangle-based packing used in Lemma 2.