Answer to Problem 14

The answer is and the graph for which this bound is achieved is a complete bipartite graph with partitions of size and , respectively. Such a graph is shown here.



Figure 11:

This graph has no triangles (every path of length 2 is an induced subgraph) and among all such graphs with 13 vertices has the maximal possible number of edges: 42.



Now for the really hard part ... can you prove that this is true?



The proof