# A hard graph theory problem on friends and enemies

Well, I guess it's to be solved using graph theory, but how? Any hints welcome.

The problem goes as follows: we have a group $n\ge 9$ people. Two people can either be enemies, friends or be neutral to each other. There are two conditions: every person has the same number of enemies and friends and there is a person, that is either a friend or an enemy of at least six people (for example, he can have three friends and three enemies).

What we need to prove is that we can make at least two people (but not specifically two) neutral to each other, but not all of them, so that in the end every person will still have the same number of enemies and friends

Any hints welcome. I guess we could try induction on $n$...? The base case seems to work, but I think its rather to be approached using graph theory. Maybe Hall's theorem?

Clarification: by "every person has the same number of enemies and friends", I mean a person $p$ must have $n$ friends and $n$ enemies and another person $p'$ has $m$ friends and $m$ enemies, but we can have $n\neq m$. And by "if two or more, but not all people become neutral", I mean that some subset of at least $2$ people are made pairwise neutral, as in every pair of people in that subset are made neutral.

• Some clarification: by "every person has the same number of enemies and friends", you mean a person $p$ must have $n$ friends and $n$ enemies and another person $p'$ has $m$ friends and $m$ enemies, but we can have $n\neq m$, right? And by "if two or more, but not all people become neutral", you mean that some subset of at least $2$ people are made pairwise neutral, as in every pair of people in that subset are made neutral? Or are these people made neutral to everybody else? – Kevin Long Sep 22 '17 at 20:30
• So every two vertices are connected with one of three colors and say this edge is white if they are neutral, red if they are enemy and green if they are friends. Every has at least 6 non white edges running out of it. Now if at least one non white edge is recolored to white then the red and green degree will stay the same at every person? – Aqua Sep 22 '17 at 20:31
• I'm afraid the world won't notice if this question goes unanswered. – Professor Vector Sep 22 '17 at 20:31
• @Kevin Long. Ad 1. Exactly. Ad 2. some subset of at least 22 people are made pairwise neutral. Sorry if it's not clear enough. – user483582 Sep 22 '17 at 20:32
• Is this a valid rephrasing? A simple graph whose edges are coloured friend or enemy has property P if every vertex has as many friend edges as it has enemy edges. Then the desired theorem is that every graph G of 9+ vertices with property P contains a subgraph G' induced by a strict subset of its vertices which also has property P, and where G' has at least two vertices. – Peter Taylor Sep 26 '17 at 11:12

Suppose integer $n\ge 9$, and adopt the edge coloring scheme on $K_n$ proposed by @JohnWatson: edges between friends are green, between enemies red, and all other edges are white.

We are given these restrictions:

• At each node the number of red edges is the number of green edges.
• Some node has at least six edges that are red or green.
• Some edge is white (neither red nor green).

Given the somewhat garbled phrasing of the Question, it seems likely to me that a further restriction may have been originally intended:

• No node has only white edges, so each node has at least one red and one green edge.

In any case we will show that some edge coloring exists to satisfy these restrictions. The case where $n$ is even is somewhat easier, because we can appeal to the existence of a $1$-factorization of $K_n$, a partition of the edges into $n-1$ parallel classes each of which is a perfect matching or 1-factor. Construction of such a $1$-factorization for even $n$ amounts to a round-robin tournament, scheduling of which has been variously described in previous Questions, e,g, here, here, and here.

So for even $n\gt 9$ we choose six of these disjoint matchings and color three of them green and the other three red (leaving the rest of the edges white). Thus every node has exactly three green edges and three red edges, and the remaining edges on any node (since $n-1 \gt 6$) are white.

For the cases where $n\ge 9$ is odd, there is no perfect matching (since it takes two nodes to make an edge). One simple idea is to "remove" a node and color the remaining complete graph on $n-1$ nodes subject to the above restrictions, but I added the final restriction (that no node has only white edges) in part to block this approach (the "removed" node would have no green or red edges). Instead we present a construction involving Hamiltonian circuits.

When $n$ is odd, Walecki's Theorem (1890s) says $K_n$ has an edge partition into $(n-1)/2$ Hamiltonian circuits, each a cycle of length $n$. If $n\ge 11$, then we can choose two Hamiltonian circuits to color green and two to color red, leaving one or more Hamiltonian circuits colored white. Since such a circuit contributes two edges for each node, all the nodes have eight edges that are green or red (and there are some white edges left over).

That leaves just the "special case" $n=9$, for which we can give a particular solution. Let's start with seven nodes and draw $K_7$ as a regular heptagon with two seven-pointed stars, as taken from Wikipedia:

This figure illustrates the Hamiltonian decomposition of $K_7$ described above, using a different color for each of the $(7-1)/2 = 3$ Hamiltonian circuits. Keeping the red and green circuits (and switching the blue one to white to "suppress" it), we have only to attach two more nodes, each with one red and one green edge to connect to a (shared) pair of the earlier nodes.

The resulting graph on nine nodes will have the latter pair of nodes with three red and three green edges, and the other conditions are also met.

• "In any case we will show that some edge coloring exists to satisfy these restrictions." I don't think this is what the question asks for. The details aren't completely clear, but the essence is definitely that for every colouring which satisfies certain conditions there is a non-trivial induced subgraph with the same colouring which satisfies certain conditions. – Peter Taylor Sep 27 '17 at 5:40
• If you read the complete comments on this Question, you'll see that I agree "the details aren't completely clear" and I (in asking clarification) got a response from the OP requesting the proof above. In any case induced subgraph doesn't seem to be the right notion because that would apply to removing nodes from the existing graph, rather than just removing edges. – hardmath Sep 27 '17 at 5:59
• My thinking with the induced subgraph is that its edges are those which should be removed from the original graph. – Peter Taylor Sep 27 '17 at 7:01