# Find the minimum number of edges in a graph with $3n+1$ vertices if ...

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?

• 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. Jul 6, 2021 at 17:11
• How does he know that $G-\{u,v,w\}$ is a graph with the same property as $G$? @BobKrueger Jul 6, 2021 at 17:32
• ah yes, of course... Jul 6, 2021 at 19:24
• 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. Jul 6, 2021 at 20:10
• Yes, that is nice observation @BobKrueger And now we can make a conjecture: for every $k$ we have $3\mid d_k$ Jul 6, 2021 at 21:42

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.