Friends exchange gifts Classmates at the end of school decided to exchange gifts. There are more than $6$ classmates. Each classmate exchanged gifts with exactly $3$ other people. Show that all classmates can be divided into $2$ non-empty groups such that each member of the group has exchanged gifts with at least two other members of the group to which he belongs.
It is easy to show that there are even numbers of students. It is also easy to show that there is a cycle in the graph. However, I cannot go further, please tell me how
 A: We rephrase the problem: show that in any $3$-regular graph, $|G|  > 6$, there exists partitions $(X,Y)$ such that every vertex in $X$ is connected to at least $2$ vertices in $X$, and similarly for $Y$. We only prove for $G$ connected, as the statement is trivial for $G$ is disconnected (if $C_1, C_2$ are components of $G$, just take partitions to be $C_1, C_2$).
Firstly, $|G|$ is even, so $|G| \geq 8$ (statement not true for $|G| = 6$).
We condition on the girth of the graph, the smallest cycle length, $g$.

Case 1: $g =3$.
Choose partitions $(X,Y)$ such that the number of edges between $X$ and $Y$, $k$, is minimum, and $|X|, |Y| \geq 3$. WLOG, suppose $v \in X$ and $v$ is not connected to at least $2$ edges in $X$. Then it is connected to $\geq 2$ edges in $Y$, and $(X \setminus v, Y \cup v)$ would be a partition with smaller $k$. If $|X \setminus v| \geq 3$, this is a contradiction, so suppose not.
This would mean that $|X \setminus v| = 2$ so $|X| = 3$ (minimum $k$ is obtained when one of the partitions have size $3$). Now we claim the following:

*

*$X$ does not have a vertex that has all $3$ of its edges connected to $Y$.

*$X$ is connected.

*There are exactly two vertices in $X$ which have two edges connected to $Y$, and exactly one vertex in $X$ with one edge connected to $Y$.

Supppose there is a vertex $v \in X$ such that all its edges are connected to $Y$. Then let $w \neq v$ be a vertex connected to $X$, and now the partition $X \setminus v \cup w, Y \cup v \setminus w$ would be a partition with smaller $k$ ($k$ is the number of edges between the partitions), contradicting $k$ being minimum. Note that the condition of both partitions having cardinality more than $3$ is still satisfied. This proves $(1)$.
$(2)$ follows immediately from $(1)$, if $X$ wasn't connected, there would be some vertex who has all its edges connected to $Y$.
For a vertex in $X$, the maximum number of edges it has connected to $Y$ is $2$. Let $n_2(X)$ denote the number of vertices in $X$ with $2$ edges connected to $Y$. Then $n_2(X) = 1,2,3$ ($n_2(X) \geq 0$ by assumption). If $n_2(X) = 3$, then the degree sequence of the subgraph induced by $X$ is $(1,1,1)$, which is not a valid degree sequence. If $n_2(X) = 1$, the degree sequence would be $(2,2,1)$, again, not valid. Hence, $n_2(X) = 2$, proving $(3)$.
These three statements combine to tell us that if we pick $3$ vertices for $X$ such that $k$ is minimised, and there is a vertex in $X$ with $\geq 2$ edges connected to $Y$, the subgraph induced by $X$ would look something like this:
   o
  /
 /
o 
 \
  \
   o

This means that between $X$ and $Y$, there would be $k = 5$ edges. Yet, as $G$ has a triangle, picking $X$ as the triangle would give only $k = 3$ edges between $X$ and $Y$, contradicting the minimality of $k$.

Case 2: $g= 4$.
Again, choose $(X, Y)$ to minimise $k$. If WLOG, there exists $v \in X$ such that $v$ has $\geq 2$ edges connected to $Y$, then the above reasoning gives the subgraph induced by $X$ must "look like" the above drawn, and have $5$ edges connecting $X$ and $Y$. Yet choosing $X$ to be the cycle of length $4$ gives a partition with only $4$ edges between $X$ and $Y$, contradicting the minimality of $k$.

Case 3: $g \geq 5$.
Then the minimum cycle length is $\geq 5$. Let $C$ be a cycle of minimum length; $X$ be the vertices involved in the cycle, $Y$ be the rest of the vertices. Then $|X| \geq 5$. Clearly, each vertex in $X$ is connected to $2$ other vertices in $X$ ($X$ is a cycle). If there exists a vertex $y \in Y$ connected to $\geq 2$ vertices in $X$, we denote the neighbours of $y$ in $X$: $n_1, n_2$ (there could be a $n_3$ if all edges incident to $y$ are connected to $X$), but we just picking $2$ is enough). $n_1, n_2$ cannot be adjacent to each other, else there would be a triangle, so $n_1$ and $n_2$ are not adjacent in $C$. Yet $n_1 \to y \to n_2 \to n_1$ gives a smaller cycle, contradiction. So all vertices in $Y$ are connected to $\geq 2$ vertices in $Y$ as well.
Lastly, we need to prove that this smallest cycle, $C$ has a cardinality $\leq n-3$. (Note: this is not true if $|G| = 6$. Draw a hexagon and connect vertices on opposite sides. The smallest cycle has length $4$, but then if we take that as $X$, $|Y| = 2$, and the condition cannot be satisfied for $Y$). This is where we will make use of $|G| \geq 8$.
Suppose the smallest cycle is $\geq n-2$ in length. Since $C$ is the smallest cycle, for every vertex in $C$, it has $2$ edges connected back to $X$ and $1$ edge connected to $Y$. So the number of 'outgoing' edges from $X$ is $n-2$. Hence $Y$, having cardinality bounded by $2$, can only receive up to $6$ edges. (Here is where $|G| \geq 8$ comes in, if $|G| = 6$, then the number of outgoing edges is only $4$, not enough to cause a contradiction since the two remainding vertices can 'accept' the $4$ edges). Since $n \geq 8$, we see that the only way this can happen is if $n=8, |C| = 6, |Y| = 2$. Yet draw a hexagon and try to find a way to connect the $2$ remainding vertices in a way that doesn't form a triangle or a smaller cycle; there's no way to do it.
Then $(X, Y)$ is a valid partition.

Understand this is a long answer, so I would be happy to answer any questions about the proof.
Edit: I understand the part about "$n_1 \to y \to n_2 \to n_1$ gives a smaller cycle" is not fully rigourous, one can refer to JPMarciano's answer for the case $k \geq 5$ for a more rigorous explaination of this, but it needs the fact that the girth of the graph is $\geq 5$.
A: Let's define $G$ to be the 3-regular graph with $V(G)$ being the students and $u v \in E(G)$ if u and v exchanged gifts. Let $C:=\{v_1,...,v_k\}\subset V(G)$ be a minimum length cycle of G.
Then $v_i v_j\in E(G)$ iff $i-j\equiv \pm 1$ $(\text{mod } k)$.
Let $A:=V(G)\setminus C$.
Case $k\geq 5$:
Suppose by contradiction that there exists $u\in A$ such that $|N(u)\cap C|\geq 2$, otherwise $A$ and $C$ are the groups as desired. Let $N(u)\cap C=\{v_i,v_j\}$ with $i<j$. Then
$$\min\{|\{v_i,v_{i+1},\dots,v_{j-1},v_j\}|,|\{v_j,v_{j+1},\dots,v_{k},v_1,\dots,v_{i-1},v_i\}|\}\leq \left\lfloor\frac{k}{2}\right\rfloor+1$$
Thus, $u$ together with one of those paths form a cycle of size at most $\left\lfloor\frac{k}{2}\right\rfloor+2<k$ as $k\geq 5$, contradicting the minimality of the cycle $C$.
Case $3\leq k\leq 4$:
For that case, a greedy algorithm adding the vertex of $A$ to $C$ whenever it has 2 neighbors in $C$ will work.
Subcase $k=3$:
Suppose by contradiction, that the algorithm only stop when $A$ is empty. Then each vertex of $G$ is in two $C_3$'s. Let $C_3(G)$ be the number of $C_3$ in $G$.
$$C_3(G)=\frac{2n}{3}\implies e(G)=\frac{2n}{3}3\cdot\frac{1}{2}=n\neq \frac{3n}{2}$$
Contradiction.
Subcase $k=4$:
Suppose by contradiction, that the algorithm only stop when $A$ is empty. Then each vertex of $G$ is in two $C_4$'s. Let $C_4(G)$ be the number of $C_4$ in $G$.
$$C_3(G)=\frac{2n}{4}\implies e(G)=\frac{2n}{4}4\cdot\frac{1}{2}=n\neq \frac{3n}{2}$$
Contradiction.
