(I'll skip over the whole "dressing" of the graph in cities and flights [Mod edit: Shu has posted the "dressed-up" version below]) For an ordinary directed graph, show that there is a subset A of vertices such that: $1.$ There are no edges between the vertices of A. $2.$ For any vertex $v$, there is either a direct way from $v$ to a vertex in A, or a way passing through only one vertex and ending in A (like $v$ ->$v'$-> $a$, where $a$ is a vertex in A)
Problem
Source:
Tags: induction, combinatorics unsolved, combinatorics
Shu
31.07.2011 19:00
Direct one-way flights run between some cities in a certain country. Prove that there is a nonempty set $A$ of cities such that there is no flight between any two cities of $A$; and from every city not in $A$, one can reach some city of $A$ either by a direct flight or by two flights with one change.
littletush
26.11.2011 07:02
we prove it by induction on the number of cities. $n=1$ trivial; if $n$ holds: then consider city $A_{n+1}$ let $B,C,D$ denote the set of cities derived from $A_{n+1}$,derives to $A_{n+1}$ and make no connection with $A_{n+1}$,respectively if the original set $A$ has a point in $B$,then it's trivial;if all points in $B$ is not in the original $A$,and they can derive some points in $C$ in one step,then let the new $C$ be the union of original $A$ and $A_{n+1}$,but exclude $C$;if there exists a point in $B$ which needs at least two steps to derive any point in $C$ then add this point to $A$. QED
junioragd
01.11.2014 17:52
I have pretty much the same solution as littleush,but I am not sure,so I will post mine.Induct on $n$.Pick a city that has at least one road that starts in him and goes to another city.Now,from the induction hypothesis,we can build a set $A$ that satisfayes the above.conditons.Now,let $B$ be the set of cityes from which we can directly come to $A$ and $C$ be the set of cityes from which we can come in $1$ change.Now,if our new city can come to $A$ or $B$,we are finished and if not than it can come to $C$,so our new set will be union of $A$ and the city from the set $C$,so we are finished.
Kayak
20.06.2018 17:59
Both the solutions are same, so I'm following junioragd's notation because that is easier to understand. To see why, consider the following graph $G$
Now for $G-v_6$ (of course you can choose other vertex to delete for induction, but the above solutions seem to not care about that and arbitrarily induct on any vertex), choosing $A = v_1$ would work (of course you can choose other vertex for $A$, but the above solution seems to not care about how the assignment to $A$ is done before the induction). But $v_6$ cannot then be in $A$ (because $v_1v_6$ edges exists), and also $v_6$'s neighbours $v_3$ and $v_2$ couldn't be in $A$ too (because $v_1v_3$, $v_1v_2$ edges exist)
(and I don't think these solutions can be fixed easily, though I may be wrong) So anybody has correct solution ?
rafayaashary1
21.06.2018 00:22
If I'm not mistaken, the following should work, no?
Let $V$ be the set of all cities in the aforementioned country and let $f:\mathcal{P}(V)\to\mathcal{P}(V)$ return, given a subset of $V$, the set of cities which may be reached by exactly one flight from a city in this subset. For all $v\in V$, the number of flights out of $v$ is then (by definition) the cardinality of $f(\{v\})$.
Let the set of all cities who lack outgoing flights be $M$. Consider some $A\subseteq V$ which has maximum cardinality among the subsets of $V$ who a.) have no flight between any two of their cities and b.) contain $M$. We claim that that for any vertex $v\not\in A$, the intersection of $f(\{v\})\cup f(f(\{v\}))$ and $A$ is nonempty (and thus that $A$ satisfies the demands of the problem).
To that end, suppose the contrary; that there exists some $\mathfrak{v}\in V\setminus A$ from which no city in $A$ may be reached by one or two flights. Then $f(\{\mathfrak{v}\})$ is clearly nonempty and disjoint from $A$, and the set $f(f(\{\mathfrak{v}\}))$ must itself be, for similar reasons, disjoint from $A$. But then $A\cup f(\{\mathfrak{v}\})$ is a set of even greater cardinality satisfying a.) and b.), a contradiction $\blacksquare$
Kayak
21.06.2018 08:18
If I'm not mistaken, the above solution is also wrong. rafayaashary1 wrote: But then $A\cup f(\{\mathfrak{v}\})$ is a set of even greater cardinality satisfying a.) How are you sure that a) is satisfied by $A\cup f(\{\mathfrak{v}\})$ since $f(A) \cap f(\{\mathfrak{v}\})$ might be nonempty? Looking at the undirected case (where taking the maximal independent set works) I previously tried to find a property $X$ (eg in the undirected case X = No two vertices are connected by an edge) such that the set $S \subset V_G$ of greatest size satisfying property $X$ would work as $A$ but that approach seemed fruitless Even induction doesn't work and the problem is probably pretty tricky.
Kayak
22.06.2018 19:05
Bump ! Any solutions ?
p_square
12.08.2018 13:50
Recently, there was a very similar codeforces question: https://codeforces.com/problemset/problem/1019/C Original paper: https://link.springer.com/content/pdf/10.1007%2FBFb0066192.pdf Note that the questions are the same if one changes the direction of all arrows in the codeforces/original paper. Proof of Tuymaada: We will prove inductively that such a set $A$ exists. Given any such graph $G$, consider deleting a vertex $v$ and all vertices $u$ such that there is an edge $u \rightarrow v$. There exists a set $A'$ of vertices in $G$ by inductive hypothesis such that all conditions are satisfied. Now, if there exists a vertex $w \in A'$ such that there is an edge $v \rightarrow w$, the set $A'$ works for the original graph $G$ as well. If there doesn't exist such a $w$, consider $A = A' \cup v$