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?
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.