# A party of jealous guys

I was really happy for the fact that I won the inter-galactic best magician award. So I decided to throw a party of $n$ people (excluding me).

The people who came to that party was jealous, really jealous of each other. Some people were not jealous of each other, but some - if not most - people, were. Jealousness, as y'all know, is mutual, so if $i$-th guy is jealous of $j$-th guy, then $j$-th guy is also jealous of the $i$-th guy.

After all the guys come, I form a special ritual called the jealousy measuring ceremony before the party: Every guy, to show off how they're good at jealousy, counts among the other $n-1$ guys total how many guys he's jealous of, and writes it down on a piece of paper and puts it inside a small green box which I prepared.

As it was a party of magicians, I brought $m$ different colored magician hats, total $n$ in number (there's at least one hat of each color) such that it's possible to put a hat on top of each of the guys, and no two persons $i$ and $j$ who are jealous of each other has the same colored hat on their head. Being the great tightwad that I am, I also ensured that $m$ is the smallest number with such property.

Now being the great magician that I am (didn't I mention that I'm also a brilliant hypnotist ?), I can pick two integers $(i,j)$ and perform a special move called wafoo: if $i$th guy and $j$ th guy are jealous of each other, remove the jealousy between them, or if they're not jealous, make them jealous of each other.

I perform a bunch of wafoo moves, and then perform the jealousy measuring ceremony again, this time using a blue box. I'll be the wafoo-master if the numbers on the paper in the green box is a permutation of the numbers of the papers in the blue box, and I can pick $m-1$ distinct integers $a_1, \cdots, a_{m-1}$ among $[1,n]$ such that for any $i \neq j \leq m-1$, the $a_i$ and $a_j$th guy are jealous of each other.

Can I always perform a sequence of wafoo moves to become the wafoo master, regardless of the initial distribution of the jealousy among the $n$ persons ?

(If you're too lazy to read the above In other words, if an undirected graph $G$ with $n$ vertices has degree sequence $\{d_1, d_2, d_3, \cdots, d_n\}$ and chromatic number $m$, prove it's always possible to construct a graph $G'$ with $n$ vertices with the same degree sequence and with $K_{m-1} \subset G$ )

• This seems to be a purely mathematical problem (it seems to require a graph-theoretical proof for a graph-theoretical claim), and as such, even the laboriously constructed story doesn't make it very puzzlingly. Puzzly. Puzzle-like. Well, you know what I mean. – Bass May 23 '18 at 14:02
• @Bass I agree, reasoning about the underlying graph-theoretic concepts without the proper language would be impossible, unless the solution were simple. And I believe the proper term is puzzlish. – noedne May 23 '18 at 14:05
• At least two 3k+rep users agree this seems to be a math problem, not a puzzle, and yet there are no votes to close it as such (and one of those two answered it anyway). Community members can, should, and are encouraged to use their voices and their votes to keep the site on topic and free from detritus. Please do so! (@Bass, $@$noedne) – Rubio May 24 '18 at 2:19
• @Rubio, it's the user's first post, and a lot of work has clearly gone into making it as puzzlificious as possible. If you want it closed, go ahead, but I don't want to greet a newcomer that way. We can, as a community, stomach a pure maths problem every once in a while, at least under such obvious attenuating circumstances. But maybe don't make a habit out of it, OP? :-) – Bass May 24 '18 at 8:44
• @Rubio Apparently you can only ping one user per comment! I think that determining whether a math problem is sufficiently puzzly requires some idea of the solution. The user framed the problem in a puzzly manner, and as I briefly mentioned in my previous comment, a simple solution to the puzzle that, say, just required a few wafoos would be a great puzzle. However, as I write in my answer, I believe the claim as stated is false. If true, this should be grounds for closing, but I don't know if it would succeed given the mathiness of my counterexample. – noedne May 25 '18 at 23:38

The claim is false. Let $n=15$ and $G$ be the complement of the disjoint union of $3$ $5$-cycles. The chromatic number of $G$ is the sum of the chromatic numbers of (the complements of) the $5$-cycles, which are $3$, so $m=9$. Let $G'$ be any graph with $n$ vertices and the same degree sequence as $G$. In $\overline{G'}$, the complement of $G'$, every vertex has degree $2$, so $\overline{G'}$ is a disjoint union of cycles. The clique number of $G'$ is the sum of the independence numbers of these cycles, which are at most half their orders, so $\omega(G')\le\frac{15}2<8=m-1$.