2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ From what I understand, the last two conditions says the graph is simple? $\endgroup$
    – user614287
    Apr 11, 2019 at 2:27
  • $\begingroup$ Yes I believe so. $\endgroup$
    – ivyleaf57
    Apr 11, 2019 at 2:29
  • $\begingroup$ 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 $\endgroup$
    – user614287
    Apr 11, 2019 at 2:40
  • $\begingroup$ Could you elaborate on the statement "Each edge takes care of 6 pairs" $\endgroup$
    – ivyleaf57
    Apr 11, 2019 at 2:42
  • $\begingroup$ I'm not really familiar with those terms. I've only be recently introduced to graph theory and I'm having difficulties understanding it $\endgroup$
    – ivyleaf57
    Apr 11, 2019 at 3:11

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .