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

Solution 1:

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

Solution 2:

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.