Extremal Triangle-free Graphs

In this talk, we will address an extremal problem from two perspectives: structural graph theory and Integer Programming (IP). We will determine the maximum number of edges in a triangle-free graph when its maximum degree is at most d and its matching number is at most m for two given integers d and m. We will derive structural properties of extremal triangle-free graphs, which will allow us i) to provide a formula for this maximum number which is valid in most cases, ii) to develop an IP formulation for constructing extremal graphs, which has surprising links with the classical Knapsack problem. We conjecture that our formula giving the size of extremal triangle-free graphs is also valid for all the open cases and endorse this conjecture by solving the IP formulation for some additional cases