, 2015

Combinatorics Difficulty 6.1 National olympiad Prove it Romania

Let $n$ be a positive integer and let $G_n$ be the set of all simple graphs on $n$ vertices. For each vertex $v$ of a graph in $G_n$ , let $k(v)$ be the maximal cardinality of an independent set of neighbours of $v$ . Determine $\max_{G \in \mathcal{G}_n} \sum_{v \in V(G)} k(v)$ and the graphs in $\mathcal{G}_n$ that achieve this value.

Solution

To prove this, let $G$ be a simple graph on $n$ vertices, and let $S$ be a maximal independent set of vertices of $G$ . If $v$ is a member of $S$ , then $k(v) \le n - |S|$ , since $v$ has at most $n - |S|$ neighbours. If a vertex $v$ is not in $S$ , then $k(v) \le |S|$ , since $k(v)$ is the size of an independent set. Consequently,
$\sum_{v \in V(G)} k(v) \le |S|(n - |S|) + (n - |S|)|S| \le \lfloor n^2/2 \rfloor.$

The complete bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$ clearly achieves the upper bound. Achieving the upper bound requires that all of $S$ be adjacent to all of $V(G) \setminus S$ and that $V(G) \setminus S$ be an independent set, so the extremal graph is unique.

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 and solution reproduced as published; topic and difficulty added by this site.