Maths Olympiad Prep

Library / /704 of 860

Combinatorics Difficulty 5.4 AIME, harder Find the answer

How many graphs are there on 10 vertices labeled 1,2,,101,2, \ldots, 10 such that there are exactly 23 edges and no triangles?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Note that the sum of the degrees of the graph is 232=4623 \cdot 2=46, so at least one vertex has degree 5 or more. We casework on the maximal degree nn. Case 1: n7n \geq 7, then none of the nn neighbors can have an edge between each other, for (n2)\binom{n}{2} edges unusable, and the vertex with maximal degree cannot connect to the 9n9-n other vertices. Then we have (n2)+9n>(102)23=22\binom{n}{2}+9-n>\binom{10}{2}-23=22 when n7n \geq 7, so there cannot be any graph in this case. Case 2: n=6n=6. WLOG suppose that 1 is connected to 2,3,4,5,6,72,3,4,5,6,7, then none of 2,3,4,5,6,72,3,4,5,6,7 can connect to each other. Case 2.1: There is at least one edge between 8,9,108,9,10, then each of 2,3,4,5,6,72,3,4,5,6,7 can connect to at most two of 8,9,108,9,10, for at most 62+(32)=156 \cdot 2+\binom{3}{2}=15 additional edges. Along with the 6 original edges, it is not enough to each 23 edges. Case 2.2: There are no edges between 8,9,108,9,10, then this graph is a bipartite graph between 1,8,9,101,8,9,10 and 2,3,4,5,6,72,3,4,5,6,7. There can be at most 46=244 \cdot 6=24 edges in this graph, so exactly one edge is removed from this graph. There are (104)24=5040\binom{10}{4} \cdot 24=5040 possible graphs in this case. Case 3: n=5n=5. WLOG suppose that 1 is connected to 2,3,4,5,62,3,4,5,6, then none of 2,3,4,5,62,3,4,5,6 can connect to each other. Case 3.1: There is at least one edge between 7,8,9,107,8,9,10. Then each of 2,3,4,5,62,3,4,5,6 can connect to at most three of 7,8,9,107,8,9,10, for 53=155 \cdot 3=15 edges. In this case at least three of 7,8,9,107,8,9,10 must not be connected to each other, so there can be at most three edges, for 5+15+3=235+15+3=23 edges at most. However, this requires the three disconnected vertices of 7,8,9,107,8,9,10 to be connected to all of 2,3,4,5,62,3,4,5,6 and the other vertex of 7,8,9,107,8,9,10, causing them to have degree 6. We can therefore ignore this case. (The case where 2,3,4,5,62,3,4,5,6 can connect to two or less of 7,8,9,107,8,9,10 can be easily ruled out.) Case 3.2: There are no edges between 7,8,9,107,8,9,10, then this graph is a bipartite graph between 1,7,8,9,101,7,8,9,10 and 2,3,4,5,62,3,4,5,6. This is a K5,5K_{5,5} with two edges removed, which accounts for (105)/2(252)=126300=37800\binom{10}{5} / 2 \cdot\binom{25}{2}=126 \cdot 300=37800 graphs. It is not difficult to see that Case 2.2 and Case 3.2 are disjoint (by considering max degree), so there are 5040+37800=428405040+37800=42840 graphs in total.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.