Graduate Program in Industrial Engineering.Taşkın, Zeki Caner.Ekim, Tınaz.Banak, Ali Erdem.2025-04-142025-04-142023Graduate Program in Industrial Engineering. TKL 2023 U68 PhD (Thes MIS 2023 S46 PhDhttps://digitalarchive.library.bogazici.edu.tr/handle/123456789/21555The maximum number of edges in a graph with matching number m and maximum degree d has been determined in [1], and a structure for an extremal graph has been provided in [2]. Then, finding the edge count of an extremal graph with forbidden subgraphs emerged as a new problem. Ahanjideh, Ekim, and Yıldız [3] worked on triangle-free graphs and solved the cases for d ≥ m and for d < m with either d ≤ 6 or Z(d) ≤ m < 2d, where Z(d) is approximately 5d/4. They also provided a structure for an extremal graph for the rest. Using the structure provided, we develop an integer programming formulation for constructing an extremal graph. The formulation is highly symmetric. We use our implementation of orbital branching and objective perturbation to reduce symmetry. We also propose an exact iterative algorithm that partitions the feasible region based on upper bounds and works iteratively on a limited space. Using a combination of the orbital branching and iterative approaches, we expand the solution into d < 11 instead of d < 7 for m > d and show that conjectures proposed in [3] hold, thus strengthening them.Maximum principles (Mathematics)Statistical matching.xi, 41 leaves