Maths Olympiad Prep

Library / /132 of 299

Combinatorics Difficulty 6.4 National Olympiad Prove it Iran

a) Prove that every graph with 2n2n vertices and n+2n+2 edges has an independent set of size nn.

b) Find the number of graphs with 2n2n vertices and n+3n+3 edges having no independent set of size nn.

Solution

a) Let AA be a maximal independent subset of vertices and BB be its complement. Assume to the contrary that AA has at most n1n-1 elements and so BB consists of at least n+1n+1 vertices. Since AA is maximal, there should be an edge from every vertex in BB to AA, so there are at least n+1n+1 edges between AA and BB. This means that there are at most 1 edge in BB let's say between uu and vv. Now B{u}B - \{u\} is an independent subset of vertices with at least nn elements, which is a contradiction.

b) We prove that the only answer is the union of two disjoint triangles and n3n-3 edges between n3n-3 disjoint pair of vertices. Let AA be a maximal independent subset of vertices, by assumption it has at most n1n-1 vertices and so its complement BB has at least n+1n+1 vertices. Similar to the previous part, we can conclude that there are at least n+1n+1 edges connecting vertices of BB to AA and there are at least 2 edges connecting vertices in BB. As the total number of edges is assumed to be n+3n+3, we deduce that AA should have exactly n1n-1 vertices and there are exactly 2 edges in BB. Also, every element of BB is connected to exactly one element of AA.

If two elements of BB, say uu and vv, are connected to some vertex wAw \in A, then uvuv must be an edge, because otherwise, (A{w}){u,v}(A - \{w\}) \cup \{u, v\} form an independent set of size nn which is a contradiction. This observation together with the fact that there are two edges in BB implies that vertices in AA can not be connected to more than two vertices in BB.

Since A=n1|A| = n-1 and B=n+1|B| = n+1, there should be two vertices x1,x2Ax_1, x_2 \in A and two disjoint pairs {y1,z1},{y2,z2}\{y_1, z_1\}, \{y_2, z_2\} in BB such that xix_i is adjacent to yi,ziy_i, z_i (i=1,2i=1,2) and so yi,ziy_i, z_i are connected. Also, there is a bijection between A{x1,x2},B{y1,z1,y2,z2}A - \{x_1, x_2\}, B - \{y_1, z_1, y_2, z_2\} such that the corresponding vertices are connected. This gives n+3n+3 edges in the graph and since there are exactly n+3n+3 edges, we conclude that the graph is the union of two triangles x1y1z1,x2y2z2x_1y_1z_1, x_2y_2z_2 and n3n-3 disjoint edges as desired.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.