# Prove minimum number of edges in a graph given constraints.

So essentially I was instructed to draw a graph with 8 vertices and 12 edges that satisfied the following constraints:

• Between every group of 3 vertices at least two are connected
• At most one connection can exist between an two vertices
• No vertex can be connected to itself

I was able to complete said graph and now I've been tasked with proving that it is impossible for such a graph to exist with fewer than 12 edges.

I was given a hint that it has something to do with each vertex having at least three connections (a degree of 3), but I don't know how one could come to that conclusion. How is it that you can just assume that each vertex has a degree of three?

• From what I understand, the last two conditions says the graph is simple? Apr 11, 2019 at 2:27
• Yes I believe so. Apr 11, 2019 at 2:29
• Ok, there are $\binom{8}{3}=56$ triple of vertices. To satisfy the first condition, Each edge takes care of 6 pairs, So we need at least $\frac{56}{6}>9$ edges. And then those groups could have intersections, so we need more edges to cover those. So pick edge $v_1v_2$, the triples $(v_1,v_2,v_3),(v_1,v_2,v_4),...(v_1,v_2v_6)$ are covered by that edge. Now, edge $v_2v_3$ covers 5 more: $(v_2,v_3,v_4),(v_2,v_3,v_5)...(v_2,v_3,v_8)$. Edge $V_3v_4$ covers 5 more... so on Apr 11, 2019 at 2:40
• Could you elaborate on the statement "Each edge takes care of 6 pairs" Apr 11, 2019 at 2:42
• I'm not really familiar with those terms. I've only be recently introduced to graph theory and I'm having difficulties understanding it Apr 11, 2019 at 3:11

Welcome to graph theory. A professional answer to your question is the following. Consider a complement $$G’$$ of the given graph $$G$$, that is $$G’$$ has the same set of $$n=8$$ vertices but any two distinct of them are adjacent in $$G’$$ iff they are not adjacent in $$G$$. That is, each edge between any two vertices belongs exactly to one of the graphs $$G$$ and $$G’$$. Thus in total $$G$$ and $$G’$$ have $${8 \choose 2}=28$$ edges. The first condition means that the graph $$G’$$ is triangle-free, that is has no cycles of length $$3$$. Then by Turán's or even Mantel's theorem, the graph $$G’$$ has at most $$\lfloor{n^2\over4}\rfloor=16$$ egdes, so the graph $$G$$ has at least $$28-16=12$$ edges.