Abstract:
The problem of maximum size of a graph of diameter 3 and maximum degree 3 as a function of its Euler characteristics is studied. The negative solution of an Erdös problem is obtained. A new approach to such problems is proposed which consists in counting the paths between different pairs of vertices in a graph.