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

Question

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?

Answer 1

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.

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

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

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

5. 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 \}$$

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

Answer 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'$.