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

combinatoricscontest-mathdiscrete optimizationextremal-graph-theorygraph theory

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?

Best Answer

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

Related Question