MathDB

min no of graphs such any 2 vertices are connected with a third vertex by edges

Source: 2009 Belarus TST 2.4

November 8, 2020

combinatoricsgraph theorygraph

Problem Statement

Given a graph with

n

(

n\ge 4

) vertices . It is known that for any two vertices

A

and

B

there exists a vertex which is connected by edges both with

A

and

B

. Find the smallest possible numbers of edges in the graph.
E. Barabanov