Airport graph theory with independent set

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Airport graph theory with independent set

G H J

Reveal topic tags

independent sets

L

G H BBookmark kLocked kLocked NReply

Source: 2022 Korea Winter Program Practice Test

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

18 posts

#1 h Aug 14, 2022, 12:25 PM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2459 posts

#2 h Aug 23, 2022, 8:36 AM • 2 Y

Y by R8kt, KevinYang2.71

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)

https://dgrozev.files.wordpress.com/2022/08/korea-tst-2.png

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.

https://dgrozev.files.wordpress.com/2022/08/korea-tst-3.png

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

659 posts

#3 h Mar 31, 2024, 9:23 PM

Y by

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.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a