Let $n\ge 2$ be a positive integer. $S$ is a set of $2n$ airports. For two arbitrary airports $A,B$, if there is an airway from $A$ to $B$, then there is an airway from $B$ to $A$. Suppose that $S$ has only one independent set of $n$ airports. Let the independent set $X$. Prove that there exists an airport $P\in S\setminus X$ which satisfies following condition. Condition : For two arbitrary distinct airports $A,B\in S\setminus \{P\}$, if there exists a path connecting $A$ and $B$, then there exists a path connecting $A$ and $B$ which does not pass $P$.
Problem
Source: 2022 Korea Winter Program Practice Test
Tags: graph theory, combinatorics, independent sets
23.08.2022 11:36
So, we have a simple graph $G(V,E)$, $|V|=2n$ and $X\subset V$ is the only independent set with $n$ vertices. We have to prove there exists $v\in V\setminus X$ which is not a cut-vertex. By considering the connected components of $G,$ it's enough to prove the following claim. Claim. Let $ G(V,E)$ be a connected graph with an unique independent set $ X$ of $ m$ vertices, and $ m\le |V|/2$. Then there exists a vertex $ v\in V\setminus X$ which is not a cut-vertex. The idea is to use induction on the number of blocks in $G$. A block is a maximal 2-connected subgraph in $G$. Adjacent Blocks in a graph overlap in their cut-vertices (as in the figure, red points are the cut-vertices) Replace each block with a large white dot, and connect each cut-vertex to every block it belongs to. The result is a a tree - fig 2, which is called the block tree. We take a block leaf in this tree, and investigate the different possibilities. There is a bit casework, but it unravels logically. More details and explanation of the needed theory can be found in my blog.
01.04.2024 00:23
Nice problem! Sketch(hard to explain without pictures): Take the obvious graph theoretic interpretation, we have a graph $\mathcal{G}(V,E)$ with $|V|=2n$ and we know $S$ is the only independent set, and thus the maximal independent set in $\mathcal{G}$, we need to prove that $\exists \quad\nu \in \mathcal{G}/S$ s.t. it is a cut vertex, to do this we induct on the number of blocks in $\mathcal{G}$, base case is obvious, for the induction step, we get that if a vertex not belonging to $S$ is adjacent to a cut vertex then we're done, we consider the block tree of $\mathcal{G}$, and consider a leaf of this tree, next we note that we have two vertices which are connected so both can't be belonging to $S$, then we notice what happens on deleting one of them, then focusing on the maximal independent sets of remaining connected components, then we take several cases, each using induction hypothesis or constructing the vertex.