Iranian Mathematical Olympiad

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

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

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

Since $|A| = n-1$ and $|B| = n+1$, there should be two vertices $x_1, x_2 \in A$ and two disjoint pairs $\{y_1, z_1\}, \{y_2, z_2\}$ in $B$ such that $x_i$ is adjacent to $y_i, z_i$ ($i=1,2$) and so $y_i, z_i$ are connected. Also, there is a bijection between $A - \{x_1, x_2\}, B - \{y_1, z_1, y_2, z_2\}$ such that the corresponding vertices are connected. This gives $n+3$ edges in the graph and since there are exactly $n+3$ edges, we conclude that the graph is the union of two triangles $x_1y_1z_1, x_2y_2z_2$ and $n-3$ disjoint edges as desired.