Let $G$ be a simple graph with $3n+1$ vertices. For any vertex $v$, there exists $n$ disjoint $K_3$ (i.e. triangle) such that none of them contains $v$. Find minimum number of edges of graph $G$.

  • If we take $n$ triangles $v_iu_iw_i$, where $1\leq i\leq n$ and a vertex $v_0$ connected with each vertex we get a graph which satysfies the condition so $\varepsilon _{\min} \leq 6n$ .

  • Now suppose there is a graph with $6n-1$ edges or less.

    Lemma Let $v$ be a vertex with minimum degree $d$ in $G$. Then $d=3$.

    Proof: By handshake lemma we have $3$: $$(3n+1)d \leq \sum _{i=1}^{3n+1} d_i \leq 12n-2\implies d \leq {12n-2\over 3n+1}<4$$ On the other hand if $d <3$ then $v$ has at most $2$ neighbours $u$ and $w$, so for $u$ we have a triangle which does not contain $u$ and does contain $v$. But then $v$ has another neighbour in this triangle (beside $w$). So $v$ has exactly $3$ neighbours.

    Claim: Every edge is present in some triangle. If not then removing it we get a smaller graph with the property same as $G$ has.

    Conjectures: Minimal configuration has exactly $4n$ triangles.

Last edit before the end of bounty.

Any suggestion how to continue?

  • $\begingroup$ It seems like the linked solution is correct to me. What is your issue with it? You have shown that the minimum degree is 3, so the removal of a triangle removes at least 6 edges, which is enough for induction. $\endgroup$ Jul 6, 2021 at 17:11
  • 1
    $\begingroup$ How does he know that $G-\{u,v,w\}$ is a graph with the same property as $G$? @BobKrueger $\endgroup$
    – nonuser
    Jul 6, 2021 at 17:32
  • $\begingroup$ ah yes, of course... $\endgroup$ Jul 6, 2021 at 19:24
  • $\begingroup$ I can't solve the problem yet, but I will just note that the extremal example is not unique: take any example for n-1, and add a triangle of new vertices to the neighborhood of some vertex to get an example for n. $\endgroup$ Jul 6, 2021 at 20:10
  • $\begingroup$ Yes, that is nice observation @BobKrueger And now we can make a conjecture: for every $k$ we have $3\mid d_k$ $\endgroup$
    – nonuser
    Jul 6, 2021 at 21:42

2 Answers 2


A little bit ahead of me. But that's the way it's going to be.

Lemma 1. Let $G$ be a graph with this property. If $a$ is a vertex of degree 3 and $b,c,d$, its neighbors, then $a,b,c,d$ form graph $K_4$.

Proof. If we remove vertex $d$, then the only triangle containing vertex $a$ is $a,b,c$. So there is an edge $bc$.

Lemma 2. Let $a$ be a vertex of degree 3 and $b,c,d$, its neighbors. Let $G'=G/\{a,b,c,d\}$ be obtained from $G$ by contracting vertices $a,b,c,d\ $ to vertex $a'$ (we remove vertices $a,b,c,d$ and add a new vertex $a'$, where the edges incident to $a'$ each correspond to an edge incident to either $b$, or $c$, or $d$). Then $G'$ is a graph with our property.

Proof. If we remove vertex $a'$ from graph $G'$, then the desired triangles are all those triangles which are obtained by removal of vertex $d$ in the original graph $G$ except for triangle $a,b,c$.

Almost similarly we find triangles if we remove vertex $x\neq a'$.


You already have several good ideas, but you are missing point 5 below.

Let's given a name to the property:

$(P)$ For any vertex $v$, there exists $n$ disjoint $K_3$ (i.e. triangle) such that none of them contains $v$.

  1. Find a family of graphs $G_n$ on $3n+1$ vertices with property $(P)$, such that $G_n$ has $6n$ edges for every $n \geq 0$

Let $G = (V,E)$ be a graph with property $(P)$ on $3n+1$ vertices and with a minimum number of edges.

  1. Using question 1, prove that there must be a vertex of degree at most 3.

  2. Prove that every vertex has degree at least 3.

  3. Let $x$ be vertex of degree 3. Prove that the set of neighbors $N(x)$ of $x$ induces a triangle $uvw$.

  4. Let $H = (V_H,E_H)$ be the graph obtained from $G$ by contracting $x,u,v,w$ into a single vertex. Prove that $H$ has property $(P)$. To be clear, $$V_H := V \setminus \{u,v,w\}\quad\textrm{and}$$ $$E_H := \{ yz~:~y,z \in V_H \setminus \{x\}, yz \in E\} \cup \{ yx~:~ y \in V_H \setminus \{x\}, \{yu,yv,yw\} \cup E \neq \emptyset \}$$

  5. Find the relationships between $|E_H|$ and $|E|$ and between $|V_H|$ and $|V|$. By induction on $n$, prove that $G$ has $6n$ edges.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .