Let us translate the statement into the language of graph theory. (It is convenient to represent non-friendships by edges, and friendships by non-edges.) Let $G=(V,E)$ be a graph. We say that $n \ge3$ different vertices $v_1, v_2, \ldots, v_n$ form a chordless cycle if $v_i$ is adjacent to $v_{i+1}$ for $1\le i \le n$ (where $v_{n+1} = v_1$), and there are no other adjacencies among these $n$ vertices. Graph $G$ satisfies the property \[\textrm{For every vertex } v \textrm{ and every chordless cycle } C \textrm{ not including } v, \\ \textrm{ at most one vertex } w \textrm{ on the cycle } C \textrm{ is adjacent to } v.\] Prove that the graph $G$ is $3$-colorable (or equivalently that $V$ can be partitioned into $3$ independent sets, or equivalently that the graph is $3$-partite)

The uncanny resemblance to the notorious Problem 3, IMO 2007, Vietnam http://www.artofproblemsolving.com/Forum/viewtopic.php?p=893746&sid=7c2f5a27231aa41d366b77aaef80e0c6#p893746, is just superficial. The difficulty levels are not quite comparable, as will be seen below.

The problem is Theorem 2.11, pages 12-13, from this article http://www.liafa.univ-paris-diderot.fr/~aboulker/propellers.pdf, where one of the joint authors is Serbian. (*) I usually resent when the main result is "hidden" into a trivial corollary. In this case, the main ingredient is the presence of a vertex of degree at most $2$; the $3$-colourability trivially follows by simple induction. So it would have been fairer to ask just this - in terms of the problem, namely that there exists a competitor who is friends with everybody, except at most two. Albeit the proof is in a way classical (an application of the extremal principle), and reasonably short, it is no wonder in the heat of the battle, and with three more other questions to boot, no-one managed to come up with a full solution to this (as I have reasons to believe). EDIT. (*) Well, I know Marko, and seemingly he would be the one proposing the problem; I paid little attention to the other name showing.

mavropnevma wrote: The problem is Theorem 2.11, pages 12-13, from this article http://www.liafa.univ-paris-diderot.fr/~aboulker/propellers.pdf, where one of the joint authors is Serbian. Two of the four authors are Serbian (Marko Radovanovic and Kristina Vuskovic).

mavropnevma wrote: In a mathematical competition, some competitors are friends; friendship is mutual, that is, when $A$ is a friend of $B$, then $B$ is also a friend of $A$. We say that $n \geq 3$ different competitors $A_1, A_2, \ldots, A_n$ form a weakly-friendly cycle if $A_i$ is not a friend of $A_{i+1}$ for $1 \leq i \leq n$ (where $A_{n+1} = A_1$), and there are no other pairs of non-friends among the components of the cycle. The following property is satisfied: "for every competitor $C$ and every weakly-friendly cycle $\mathcal{S}$ of competitors not including $C$, the set of competitors $D$ in $\mathcal{S}$ which are not friends of $C$ has at most one element" Prove that all competitors of this mathematical competition can be arranged into three rooms, such that every two competitors in the same room are friends. (Serbia) Does anybody know how many contestants have solve it at BMO?

mavropnevma wrote: Albeit the proof is in a way classical (an application of the extremal principle), and reasonably short, it is no wonder in the heat of the battle, and with three more other questions to boot, no-one managed to come up with a full solution to this (as I have reasons to believe). Have you read this comment? The results have been posted, but only the medals, not the actual points per problems. However, I have a strong belief nobody solved it in its entirety - the highest scoring in the competition, with 36/40 points, got 6/10 on it, and this could easily be the best result achieved.

The article calls a special graph, made by a chordless cycle (named rim) and a center, connected to at least two vertices on the rim, a propeller. Under this terminology, our graph is propeller-free, and $3$-colourable (by the proof of the theorem).

I am not sure if I am right, but continuing solving the problem after manuel153 reformulation, I get the following: We prove the fact by induction. Base case $n=3,4$ is true. Having $n$ vertices, pick a vertex $v$ and consider graph $G\backslash v$. The initial statement still holds for $G\backslash v$. So there is a $3$-coloring for $G\backslash v$. Then we have two cases: a) Neighbors of $v$, when we color $G\backslash v$, are colored in at most two colors. Color $v$ with the third color, and we are done. b) There are three neighbors of $v$ that are colored in distinct colors. They form a $3$-cycle, and $v$ can be connected to at most one of them, a contradiction. Seems to be not difficult at all. I am wondering if there is a mistake in my thought process.

Yes, there is a (big, irrepairable) mistake. Those three neighbors that are colored in distinct colors; why do they have to form a $3$-cycle? There may not even be one edge between any two of them. That is the whole point to the problem, I was referring to in my post. In order to solve the problem, one must have the courage and set to prove the stronger statemenet that such a graph must have a vertex of degree at most $2$; then induction works by removing that vertex. And indeed, this is the course to go. Once you decide to go this way, the solution is a one-liner, by considering a longest chordless path in the graph; then each of its ends has to have degree at most $2$.

@mavropnevma In your example $abcde$ is a rim, and $f$ is connected to $b, c, d$. Isn't that a wheel?

True! And so is in fact $abcdg$ a rim, with $f$ the center of a wheel. I was trying to produce a minimal example, and overlooked the longer cycles that may be rims. So the question remains open (for the moment); are all wheel-free graphs $3$-colourable?

Btw, in the article you provided they define a wheel as a rim at least 4 in lenght and a center, connected to it by at least 3 edges. So strictly $K_4$ isn't a wheel and the question is a puff But I still strive to construct your-wheel-free graph, that is not 3-colourable.

Hey! Quote: It is also proved that ... every $K_4$ free graph that does not contain a wheel is 3-colorable. So what were you proposing us to construct again? Seriously, I've spent an hour trying to get it done.

amatysten wrote: Btw, in the article you provided they define a wheel as a rim at least 4 in lenght and a center, connected to it by at least 3 edges. So strictly $K_4$ isn't a wheel. Yes, I know, but that decision seems arbitrary. Later on in the article, they define a $4$-propeller when the center has at least four neighbours on the rim, with no extra condition as to the length of the rim. So in general we can define a $n$-propeller when the center has at least $n$ neighbours on the rim (with the only obvious condition the rim has length at least $n$). Thus, it seems reasonable, according to the article, to call a $2$-propeller simply a propeller, and to call a $3$-propeller a wheel. The problem proved that a propeller-free graph is $3$-colourable (because it contains vertices of degree at most $2$). My question is: will a wheel-free graph also be $3$-colourable? or can we exhibit a counter-example?

As I cited from article every $K_4$ free graph that does not contain a wheel is 3-colorable. So counterexample can't be built.

Finally, I got your drift. To summarize, the article states $\bullet$ "Clearly, propeller-free graphs form a subclass of wheel-free graphs, because every wheel is a propeller." at page 2; indeed, trivial (from definitions). $\bullet$ "It is also proved there that every graph that does not contain a wheel is $4$-colorable, and that every $K_4$-free graph that does not contain a wheel is $3$-colorable." at page 3. My question was if every ($K_4$-free that is also) wheel-free graph is $3$-colorable. That means a graph that does not contain a wheel as an induced subgraph; the above cited result only applies to a graph that does not contain a wheel (as a subgraph, not necessarily induced), and this class of graphs is clearly more restrictive than the class of wheel-free ones (see a similar statement on $\mathcal{C}_1 \subsetneq \mathcal{C}_2$ at page 12). So my question still stands, open. If it turns out that wheel-free graphs are $3$-colorable, then so will be the propeller-free ones (as being a subclass).

It seems I don't clearly understand what "contain" means nowadays, sigh... Well, just another thing to learn, I guess. Thanks.

The fault is with the article. Their definitions are, at page 2, 1) "We say that a graph $G$ contains a graph $F$ if $F$ is isomorphic to a subgraph of $G$" 2) "We say that $G$ contains $F$ as an induced subgraph if $F$ is isomorphic to an induced subgraph of $G$" 3) "We say that $G$ is $F$-free if $G$ does not contain $F$ as an induced subgraph" So when one says $F$-free, one is using definition 2), meaning no induced isomorphic subgraph. A little confusing all these, I agree.

Can you please wrote some proof with "pure mathematics" not hard graph theory or set theory ? Thanks.

So you think "hard graph theory", or "set theory", are not "pure mathematics"? All we use from there is the terminology, that should make the problem easier to understand and deal with, and (inevitably) some borrowed techniques. There is no proof in one-syllable words ...

sorry sorry i mant just to decribe solutioj with just elementary set theory ... i will try to do this also ... i meant no easy to do do so ...

i meant "translate" in as simple as possible the solution to the language set theory or graph thepry as simple as possible ... just to use only high school techniques ... it is difficult to do for such kinds of problems bt we can try to do it as simple as possible

Now that mavropnevma's link to the article has broken, it seems that there is no solution... We present a proof to manuel153's version. Firstly, we show that there is one vertex with degree at most $2$. Consider the longest path $P$ where no two vertices in the path are connected to each other, and suppose for contradiction that all vertices in $G$ have degree at least three. Let one end of $P$ be the vertex $x$. Now $x$ is connected to two vertices not in $P$, say $y,z$. Then $y,z$ must each be connected to at least one vertex in $P$, since otherwise $P$ may be extended to include $y$ or $z$, contradicting the maximality of $P$. Suppose $y, z$ are connected to $y_P ,z_P \in P$, not necessarily distinct. WLOG, assume $y_P$ is at least as close to $x$ as $z_P$ is. Then $y$ is connected to both $x$ and $y_P$, which are both part of the cycle $y_P , \dots , z_P , z, x, \dots , y_P$. But this contradicts the condition in the problem, hence there must be a vertex with degree at most two. mavropnevma wrote: In this case, the main ingredient is the presence of a vertex of degree at most $2$; the $3$-colourability trivially follows by simple induction. We spell out this induction: that the graph is $3$-partite if there is a vertex with degree at most two. The base case is trivial. Suppose the graph is $3$-partite if its order is less than $k$. For a graph with order $k$, take the vertex of degree at most $2$ and remove it: the resulting graph is $3$-partite by the induction hypothesis, and we are done. EDIT: Actually, you can see the article here.

Rephrase the problem as follows: OTIS wrote: Let $G$ be a graph with the property that for any chordless cycle $C$ and any vertex $v$ not in $C$, at most one vertex of $C$ is adjacent to $v$. Prove that $G$ is three-colorable. We aim to show the existence of a vertex with degree less than 3 through contradiction. Consider a chordless path of maximal length, with vertex $v$ as one of the endpoints. Our contradictory assumption tells us this vertex is adjacent to two others (not on the path), say $v_1$ and $v_2$. Maximality tells us $v_1$ and $v_2$ each must be adjacent to a vertex on the path, leading to a contradiction of the problem statement. Thus any graph satisfying the conditions has at least one vertex with degree less than or equal to 2. Note these vertices do not affect colorability, so we simply delete them to form a new graph satisfying the problem statement, and so on. $\blacksquare$

Rephrase the problem as follows: Let $G$ be a graph with the property that for any chordless cycle $C$ and any vertex $v$ not in $C$, at most one vertex of $C$ is adjacent to $v$. Prove that $G$ is three-colorable. Clearly disconnected components do not affect each other's colorabilities, so we will consider each connected components one by one. Thus, assume that $G$ is connected. Then note that we cannot have any non-chordless cycles, as we can take the smallest chordless cycle in such a cycle and get that there could only be at most one vertex adjacent to it. Thus, there are only three ways for a connected component to look. 1. A chordless cycle connected to a chordless cycle. 2. Some acyclic component. 3. Chordless cycles connected to some acyclic component. Now suppose we have three colors $0,1,2$. We will show that we can three-color each one of such cases. In the first case, we know that a chordless cycle is $3$-colorable as odd cycles are $3$-colorable while even cycles are $2$-colorable. So we can independently $3$-color the two cycles, now suppose they are connected by $u \in C_1, v \in C_2$. If $u,v$ are different colors we are done. If $u,v$ are the same color we can pick $C_2$ and shift every color up by $1$, interpreting the colors mod $3$. If we are in the second case, then clearly it is $3$-colorable as acyclic components are $2$-colorable. If we are in the third case, we can independently color the acyclic component and the chordless cycles. Call the acyclic component $A$ and the cycles $C_1, \ldots, C_k$. Then, fix the coloring of the acyclic component and shift the coloring of all $C$ until every $v_i \in A$ adjacent to $u_1,\ldots, u_j \in C_1, \ldots, C_j$ has the color of $u_1=\cdots=u_j \neq v_i$.

Wow this is an incredibly terrible writeup but anyway: Call the graph $g$, take the complement graph $g'$, thus the condition becomes prove that $g'$ is $3$ partite if for every competitor $C$ and every cycle at most one member of the cycle is connected to $C$. Now I will induct, it is plain that the result holds for a graph with $1$ vertice, now suppose it holds for a graph with $n-1$ vertices. Thus it suffices to prove that for one of the $3$ groups in the $3$ partite partion for $n-1$ the $n$th vertice does not connect to any members. We can extend the condition about cycles, suppose we have a cycle that has a path from one of the vertices in it to another vertice in it that isnt part of the cycle, then that entire cycle plus the path can only have one connection to the $n$-th vertice call such a thing a large cycle. Thus we only need to consider, large cycles that are not themselves part of a large cycle as each large cycle can have at most one connection with the $n$-th vertice. Note that if we have disconnected graphs we can rotate them freely around each other, so as both have a partition for the $3$ partite individually that doesnt connect to $n$ it works as we can rotate them to be the same part of the overall partition. Now suppose two large cycles are connected by an edge, as they are connected by an edge we don't have total freedom over how we can place the $1$ vertice that has a connection with $n$, however we have two choices, and by repeatedly choosing a choice so we always have a partite with no connection with $n$ we win.

See here for the article Mavropnevma commented.

Let the degree of each vertex be at least 3. We will show, using contradiction that there is a vertex u with $d(u) \leq 2$. Lets take the chordless path of maximal length, where one of the endpoints is vertex v. Now v has degree at least 3, but it cant be connected with an edge to any of the other vertices on the path. Let it be connected with an edge to $v_1$ and $v_2$ outside the path, but now we get a longer path - contraduction with our take for longest path $\Rightarrow$ $v_1$ and $v_2$ should be adjacent to some vertices on the path, but they are already adjacent to v $\Rightarrow$ they are adjacent to more than one vertex on the path - contradiction with the statement $\Rightarrow$ there is a vertex u, with $d(u) \leq 2$. Now these vertices don't affect the coloring $\Rightarrow$ we can delete them. By induction we can always delete such vertex with $d(u) \leq 2$ $\Rightarrow$ we can continue deleting etc etc $\Rightarrow$ G is 3-colorable and we are ready.