Let the largest matching in this multigraph be $(u_1, v_1), (u_2, v_2), \dots, (u_k, v_k)$, so there is an edge between $u_i, v_i$ for all $1 \le i \le k$. Let $M$ be the set of the $2k$ vertices in the above matching. For any vertex $v \in M$, let $\deg v$ denote the number of edges from $v$ to other vertices in $M$, not vertices not in $M$. Also for any vertex $v \in M$, define $o(v)$ to be the number of edges from $v$ to vertices not in $M$. Let $e$ be the number of edges among vertices only in $M$. Since the above matching is the largest, we cannot have edges $u_ix_i$ and $v_iy_i$, where $x_i \not= y_i$, and they are vertices in the graph, but not in $M$. Otherwise, we can increase the matching just by deleting edge $u_iv_i$ and adding in edges $u_ix_i$ and $v_iy_i$. Now I claim that $o(u_i)+o(v_i) \le 3n - \frac{\deg u_i + \deg v_i}{2}$. The proof has 2 cases: Case 1: $o(u_i) = 0$ or $o(v_i) = 0$. If $o(u_i) = 0$, then clearly $o(u_i)+o(v_i) \le 2n- \deg v_i$ since the number of edges to $v_i$ is at most $2n$. But $2n - \deg v_i \le 3n - \frac{\deg u_i + \deg v_i}{2}$ reduces to $\deg u_i \le 2n+\deg v_i$, which is trivial. Case 2: Otherwise, there must exist a vertex $w$ such that the only edges from $u_i, v_i$ to vertices not in $M$ are to $w$. This case gives us the inequality $o(u_i)+o(v_i) \le \min(2n, 4n - \deg u_i - \deg v_i) \le \frac{6n - \deg u_i - \deg v_i}{2} = 3n - \frac{\deg u_i + \deg v_i}{2}$. So the lemma is proven. Summing $o(u_i)+o(v_i)$ over all $i$ gives $3nk - \sum \frac{\deg u_i + \deg v_i}{2} = 3nk - e$. Including the $e$ edges within $M$ back in, we get $3nk$ total edges. The construction is as yugrey describes above.

Just wondering, what would you rate this problem's difficulty, say on the IMO?

I don't know what are the vertices of the graph, and why the number of edges equal to the number of kids

Since each kid chooses 2 distinct candies, we can think of each kid as an edge and each candy as a vertex, since each edge connects 2 vertices. Note that in this graph we can have multiedges though, that is, multiple edges between a pair of vertices.

But if one kid has 3 candies colour 1,2,3 then he is edge of 12, 23,31, so the number of kids is not a number of edges. or i don't understand this sentence: A couple of kids each buys from the vending machine $2$ candies of different colours. So i can't see that each kid choose 2 diffirent candies and also have a quesstion above. Can you help me to understand?

Sorry for not responding earlier. The problem says that each kids selects EXACTLY TWO CANDIES of different candies from the machine. I think you misunderstood the problem.

Let $G$ be a multigraph without loops (i.e. multiple edge between two vertices are possible, but no edge with the same endpoints), such that its vertices correspond to the colors of the candies and the edges correspond to the kids. Then, given $k,n$, we want to find the maximal $|E|$ such that among every $k+1$ edges, there are two which are adjacent (sharing at least once vertex). Additionally, the degree of each vertex is $\le 2n$. We claim that $\max |E| = 3kn$. Construction: Consider a triplet of vertices, with $n$ edges between every two vertices, then duplicate until $k$ copies in total. Clearly, among $k+1$ edges, two of them belong to the same copy and are hence adjacent.

But by Shannon's theorem, any such graph can have its edges colored in $\le \frac{3}{2}\Delta$ colors (where $\Delta$ is the maximum degree). So one of the colors must have at least $k+1$ edges which are all non-adjacent.

We may assume that there exists a $k$-set of edges that don't share vertices $\{(A_i,B_i) : i=1,...,k\}$ and let $X$ be the $2k$-set of these vertices. If $A_i, B_i$ have edges exiting $X$ then they must be adjacent to the same vertex $C_i$. Let $E_i$ be the number of edges from $A_i$ or $B_i$. In this case, since the degree of $C_i$ is $\le 2n$, then $E_i \le 2n$. Also, let $a_i,b_i$ be the degree inside of $X$ of $A_i$ and $B_i$, and we get $E_i \le 4n-(a_i+b_i)$ and so $E_i \le \text{min}\{4n-(a_i+b_i),2n\} \le 3n-(a_i+b_i)/2$. If this is not the case then WLOG $A_i$ has no edges exiting $X$. Then $E_i \le 2n-b_i \le 3n-(a_i+b_i)/2$. So $E_i \le 3n-(a_i+b_i)/2$ and then we count the number of edges by adding: it's $3nk$. Construction: $k$ triangles.

The problem can be restated as follows: consider all multigraphs with maximum degree $2n$ such that its maximum matching has size at most $k$. Find the maximum number of edges in such a graph. We claim that the answer is $3kn$. This can be constructed easily by taking $k$ triangles, each of which consist of $3$ vertices with $n$ edges between each pair. Now suppose some multigraph $G$ satisfies the above properties and $v_1w_1$, $v_2,w_2,\cdots v_\ell w_\ell$ are a maximum set of $\ell$ non-adjacent edges of $G$ for some $\ell\le k$. Let $S$ consist of all vertices $v_i$ or $w_i$, and let $T$ consist of the rest of the vertices of $G$. Clearly, $G$ restricted to $T$ must be an independent set, or we could add another edge into the matching. Also, note that if for some $i$, $v_i$ is adjacent to $x$ in $T$ and $w_i$ is adjacent to $y$ in $T$, then $x=y$, or we could replace $v_iw_i$ with $v_ix$ and $w_iy$. Now for each $i$, let: $a_i$ be the degree of $v_i$ restricted to $T$ $b_i$ be the degree of $w_i$ restricted to $T$ $c_i$ be the degree of $v_i$ restricted to $S$ $d_i$ be the degree of $w_i$ restricted to $S$ Note that $a_i+b_i\le 2n$, even if one of them is $0$, since any edges from $v_i,w_i$ into $T$ must go to the same vertex. If some edges from $v_i,v_j$ or $v_i,w_j$ connect to the same vertex in $T$, this only makes the bound stronger. Since there are no edges within $T$, the total number of edges in $G$ is \[ E=\sum_{i} a_i+b_i+\frac{c_i+d_i}{2} \] We claim that for each $i$, $a_i+b_i+\frac{c_i+d_i}{2}\le 3n$. Indeed, note that $c_i\le 2n-a_i$ and $d_i\le 2n-b_i$ so \[ a_i+b_i+\frac{c_i+d_i}{2}\le 2n+\frac{a_i+b_i}{2}\le 3n \] so this implies \[ E\le 3\ell n\le 3kn \] as desired.

I'll use pi37's setup with a multigraph $G$ such that all vertices have degree $\le 2n$ and the maximum matching has size $k$. Then I'll prove there are at most $3kn$ edges, with equality for example with $k$ triangles. Consider the maximal matching $M = \{ a_1b_1, \dots, a_kb_k \}$. Then every edge in $G$ touches a vertex in $M$. Call an edge dangling if it touches exactly one vertex in $M$. Claim: Every edge $e = ab \in M$ can be attached to at most $2n$ dangling edges. Proof: If not, then we see there are dangling edges $av$, $bw$ with $v \neq w$, contradicting maximality of $M$. The sum of the degrees of vertices in $M$ is $4kn$; there are at most $2kn$ dangling edges ("cost 1"), and all other edges touch two vertices in $M$ ("cost 2"). So number of edges it at most $2kn + \tfrac12(2kn) = 3kn$.

Nice problem! 61plus wrote: Fix positive integers $k,n$. A candy vending machine has many different colours of candy, where there are $2n$ candies of each colour. A couple of kids each buys from the vending machine $2$ candies of different colours. Given that for any $k+1$ kids there are two kids who have at least one colour of candy in common, find the maximum number of kids. Answer. $\boxed{3nk}$. Solution. Consider the graph $G$ with colours of candies as vertices and kids as edges. According to the given conditions, $G$ has no vertex of degree higher than $2n$; has no matching of more than $k$ edges. Our objective is to maximise the number of edges of $G$. Pick a maximum matching $M=X \cup Y$ of $G$, with $m \le k$ edges. Suppose $X=\{X_1, \dots, X_m\}$, $Y=\{Y_1, \dots, Y_m\}$, and $X_i$ matches to $Y_i$ for all $i\le m$. Let $x_j$ denote the number of edges $X_j$ has leading to vertices aside from those in $M$. Define $y_j$ similarly. Claim. $x_j+y_j \le 2n$ for all $1 \le j \le m$. (Proof) If $\min(x_j, y_j)<1$ then the claim is true because $\max\left(\text{deg}(X_j), \text{deg}(Y_j)\right) \le 2n$. Else, notice that by maximality of $M$, for any vertices $U, V$ outside $M$, both of $UX_j$ and $VY_j$ cannot be edges of $G$. Hence, $(x_j+y_j)$ simply counts the degree of a common neighbour of $X_j$ and $Y_j$; so $(x_j+y_j) \le 2n$. $\blacksquare$ Finally, we remark that each edge of $G$ has a vertex in common with $M$, again due to maximality. Counting the number of edges, by degrees of vertices in $M$, we see that $$E=\sum^m_{j=1} \left(x_j+\tfrac{1}{2}(2n-x_j)\right)+\sum^m_{j=1} \left(y_j+\tfrac{1}{2}(2n-y_j)\right)=\sum^m_{j=1} \left(\tfrac{1}{2}(x_j+y_j)\right)+2nm \le 3nm \le 3nk$$as claimed. Observe that $k$-triangles, each with $n$ edges satisfy the condition, hence the bound is attained as well. $\blacksquare$ Remark: $G$ is actually a multi-graph, but that's not anything serious to worry about.

Consider a graph $G$ where the vertices are the colors, and we connect two colors once for each kid that chooses those two colors. Note that $G$ is a multigraph (but no loops). Then, the problem is telling us that the largest matching has size $k$, and that the degrees are bounded above by $2n$. Note that a matching is a subset of the edges such that no two edges in that subset share a vertex. We claim that the maximal number of kids is $3nk$. Equality can be achieved by considering $k$ disjoint triangles with each edge repeated $n$ times. Consider a maximal matching (no edges can be added to make it larger), and suppose it has size $m$. Now, let $T$ be the sum of the degrees of all the vertices in the matching. This counts every edge twice, except those edges that have only one vertex in the matching (if some edge had none in the matching, then the matching could be made bigger by adding that vertex). Call these edges unfaithful. We claim that the number of unfaithful edges adjacent to a particular edge in the matching is at most $2n$. If this wasn't the case, by pigeonhole, we could find two disjoint unfaithful edges, one adjacent to one vertex of the original edge, one adjacent to the other. By picking these two, and removing the original edge, we would get a bigger matching. Thus, the number of unfaithful edges is at most $2mn$. But $T\le (2m)(2n)=4mn$, and $T$ plus the number of unfaithful edges is as we noted twice the total number of edges, so the total number of edges is at most $3mn\le 3nk$, so the total number of kids is at most $\boxed{3nk}$, as desired.

Same solution as above posts, but posting for storage anyway. Very nice problem!

Nice problem!(Despite getting scammed) Solved with Rg230403 First, we make a natural change. Replace candies with ice creams because they're nicer. Rephrase the problem with graph theory with vertices as ice cream flavors and an edge between them if there is a kid who chose these two flavors. (It's a multigraph) We claim the answer is $3nk$, which can be achieved by taking $k$ triangles and in each, an edge weight of $n$, which satisfies the condition and has exactly $3nk$ edges. Now, consider the graph that gets the most number of edges and consider its maximal matching, which has size $k$ because if not, just add another edge. Note that every edge has at least one vertex as part of the matching, as otherwise we could just add it. Call a vertex saturated if its degree is $2n$. See that if $ab$ is any edge in the graph, then at least one of the vertices is saturated, or we add $ab$ again. Suppose $xy$ is an edge in the matching. There are two possible cases, first, if one of them has no neighbours outside the matching. Then the other is saturated and so these two together have $2n$ neighbours outside the matching. Now suppose both of them do have a neighbour outside. Observe that they must have the same set of neighbours. If not, say $x$ is connected to $p$ and $y$ to $q$. Then $xp$ and $yq$ together form a $k+1$ matching. So, once again they have at most $2n$ neighbours outside the matching. We are basically done now. Inside the matching, the sum of degrees is at most $(2k)(2n) = 4kn$ and for outside the matching, it is at most $(2n)(k)$ by the previous paragraph. Since every edge has a vertex from the matching, this means that the total sum of degrees is at most $4kn + 2kn = 6kn$. So, the number of edges is at most $3kn$, as desired. $\blacksquare$

Easy for a China TST 3? The answer is $3nk$. Let the colors of the candies be $c_1,c_2,\ldots$. Then for a construction, let $n$ kids each take candies of the colors $\{c_{2i-1},c_{2i}\}$ for $1 \leq i \leq k$. Then let $n$ kids each take candies of the colors $\{c_{2i-1},c_{2k+i}\}$ and $n$ kids each take candies of the colors $\{c_{2i},c_{2k+1}\}$ for $1 \leq i \leq k$, for a total of $3nk$ children. Note that any two kids who take a candy colored in $\{c_{2i-1},c_{2i}\}$ for $1 \leq i \leq k$ must share at least one candy colored in common. As such, if some set of kids exists such that no two kids have a common-colored candy, there can only be one kid who takes a candy of color in $\{c_{2i-1},c_{2i}\}$ for each $1 \leq i \leq k$, for a total of at most $k$ kids. Now we prove that this is maximal. Consider an assignment of candies that has a maximal number of children. Then there must exist some set $S$ of $k$ children who do not share any colored candies in common, otherwise we can just add another kid arbitrarily (say, with two uniquely-colored candies). Write $S=\{a_1,\ldots,a_k\}$, where each $a_i$ is a child who WLOG has candies colored $c_{2i-1},c_{2i}$. Then, any other child must have at least one candy whose color is in $c_1,\ldots,c_{2k}$. Call a kid who has exactly one candy colored one of $c_1,\ldots,c_{2k}$ quirky, and refer to the set $\{c_{2i-1},c_{2i}\}$ as "color group $i$" for $1 \leq i \leq k$. Consider two quirky children $C_1,C_2$ with candies colored $c_{2i-1},c_x$ and $c_{2i},c_y$ respectively. If $x \neq y$, then the set $S \cup \{C_1,C_2\} \setminus {a_i}$ has $k+1$ kids who don't share any same-colored candies, which is not allowed. As such we must have $x=y$. This means that the candy colors of the quirky children in some color group $i$ follow two possibilities: All of the quirky children share a candy color in color group $i$, so there are at most $2n-1$ quirky children there. Not all of the quirky children share a candy color in color group $i$, but they do share a candy color outside of color group $i$, so there are at most $2n$ quirky children there. Combined, this means that there are at most $2n$ quirky children for each color group, for a total of $2nk$. Letting $N$ denote the number of quirky children in total, one can check that we can have at most $\tfrac{4nk-N}{2}$ non-quirky children, since there are $4nk-N$ candies of color $c_1,\ldots,c_{2k}$ not already taken by quirky children, and each non-quirky child must take two candies of color $c_1,\ldots,c_{2k}$. As such, it follows that the total number of kids is at at most $$N+\frac{4nk-N}{2}=2nk+\frac{N}{2}\leq 3nk,$$as desired. $\blacksquare$

Wall of text inbound. We claim that the answer is $3kn$. Claim: $3kn$ can be achieved. Proof. Call a triplet three kids that have pairs $\{a, b\}$, $\{b, c\}$, and $\{c, a\}$ for some candies $a, b, c$. Then take $k$ disjoint triplets, each duplicated $n$ times. By pigeonhole among $k + 1$ kids, there must be two in the same triplet which means this holds. $\blacksquare$ We now show that this is maximal. This is equivalent to the size of a multigraph with kids as edges such that each vertice has at most degree $2n$, and the maximal matching has size at most $k$. Claim: Assuming that the degree condition still holds, replacing one kid with a copy of another retains the maximal matching. Proof. Suppose that edge $b$ is replaced with a copy of $a$. This preserves the size of the multigraph evidently. Now consider sets of $k + 1$ kids. Any set not containing $b$ must still not be a matching. Any set containing $b$ and not $a$ becomes a set already present. Any set containing both $a$ and $b$ now has at least two copies of $a$, and thus can't be matching. $\blacksquare$ Note that we can add a kid that is the same as previous kid similarily. Repeat this until every edge has at least one vertex of degree $2n$. Claim: Every vertex must have degree $2n$ if maximal. Proof. If the two edges of a vertex both have degree less than $2n$, then adding an edge between them increases both of their degree. Furthermore, if $A, B, C$ are vertices connected in that order, by moving the edge from $A$ to $B$ to the one the edge from $B$ to $C$, we can decrement the degree of $A$ by $1$ and increment the degree at $B$ by $1$. We can reduce to connected components. First, assume that the component has an odd cycle. By repeating the above operation, we can reduce the degree of any vertex and increase the one of another vertex. We can repeat that to get adjacent vertices with degree less than $2n$ until all but one vertex has degree $2n$, with the last one having either degree $2n - 1$ or degree $2n$. Only the latter is possible since the sum of all degrees is even. Now, suppose that the component has an odd cycle. Then we can $2$-color the component. Similarily, we can subtract one from the degree of one vertice and increment the others if they have the same color. By using this, we can repeat this until the degrees of vertices of one color is all $2n$, and degrees of the other are all $2n$ except for at most one. Then the last vertex must also have degree $2n$ as the difference between the sum of degrees of one color and the other must be zero. $\blacksquare$ Thus, the number of edges is $\frac{2n}{2} = n$ times the number of vertices. Now, take a component. If it has an even cycle, by replacing one set of alternating edges in the cycle with another we maintain the conditions. We can repeat this until there are no nontrivial even cycles. Claim: There is at most one odd cycle. Proof. If there are more than one odd cycle, since the component is connected we can merge them to get an even cycle (potentially repeating vertices) that we can replace on, contradiction. $\blacksquare$ Claim: The component is a cycle. Proof. If not, there must be some vertex with only one neighbor. However, since both the vertex and the neighbor have degree $2n$, this implies that they are disconnected, contradiction. $\blacksquare$ As such, for a component of size $n$ we can get a matching of size $\left\lfloor \frac{n}{2} \right\rfloor$. It remains to maximize $a_1 + a_2 + \dots + a_m$ where $\left\lfloor \frac{a_1}{2} \right\rfloor + \left\lfloor \frac{a_2}{2} \right\rfloor + \dots + \left\lfloor \frac{a_m}{2} \right\rfloor = n$ such $a_i$ are integers at least $2$. Since $\left\lfloor \frac{a + 2}{2} \right\rfloor = \left\lfloor \frac{3}{2} \right\rfloor + \left\lfloor \frac{a}{2} \right\rfloor$ we can assume that each $a_i$ is $2$ or $3$. Then, since $\left\lfloor \frac{2}{2} \right\rfloor = \left\lfloor \frac{3}{2} \right\rfloor$ it follows that this is maximized when $a_1 = a_2 = \dots = a_k = 3$ and $m = k$. Since this gives a maximum of $3k$ vertices, there's a maximum of $3nk$ edges.

Nice problem. The key is to interpret the problem as a multigraph $G$ on the set of colors, such that two colors are connected by an edge if and only if some kid chooses both colors. The conditions are equivalent to $\deg v \leq 2n$ for all $v \in G$, and that the maximal matching has size $k$. Consider such a maximal matching of the form $u_iv_i$ for $1 \leq i \leq k$. It follows that every edge in $G$ must be connected to one of the $v_i$ and $u_i$. The key claim is the following: Claim. For each vertex $u_iv_i$, there can be at most $2n$ edges pointing from one of the two vertices to a vertex not among the $u_i$ and $v_i$. Proof. We will really analyze how these edges could exist. Notice that if there exists two vertices $a, b$ such that $u_ia$ and $v_ib$ are both edges, then we have a contradiction of the maximal matching. Therefore, the greatest possible total number of edges is $2n$, attained when $2n-1$ edges are pointing from $u_i$ to a vertex $a$ and one edge is pointing from $v_i$. $\blacksquare$ It follows that the total number of edges is at most $2kn + \frac 12(2kn) = 3kn$ by double counting the edges among the $u_iv_i$, as needed. Equality can obviously hold.

Very nice problem from a CHNTST !! We claim the answer is $3nk$; let the colors be $C=\{c_1,...,c_k\}$. For the construction, interpret as a multigraph where an edge represents a kid selecting two colors' candies (colors are vertices). Then simply take k triangles, with n edges between any two vertices; it's obvious this works by Pigeonhole. Now take the maximal \# of children; by maximality there must exist a set $S=\{a_1,...,a_k\}$, where each $a_i$ is a kid who WLOG has candies colored $c_{2i-1},c_{2i}$ (that is, their colors are all pairwise distinct), call these kids \texit{normal}. Then, by the condition call the other kids $b_1,...:|b_i\cap C|=1$ \textit{special}; furthermore $|b_i\cap b_j|=1$, for otherwise $\lvert\{\{C\setminus\{C\cap b_i,C\cap b_j\},b_i,b_j\}\rvert=k+1$ has no common elements. As a result, there's at most 2n special kids for each group $\{c_{2i-1},c_{2i}\}$, so there's $s\le 2nk$ special kids. Evidently there's at most $\frac{4nk-s}{2}$ normal kids, whence the total \# of kids is at most $N+\frac{4nk-N}{2}=2nk+\frac{N}{2}\leq 3nk$, as claimed. $\textbf{Remark.}$ This is pretty much the same as the other solutions -- I just found it more natural to phrase in terms of set theory.

Could someoen check mine. We claim if we have more than $3nk$ edges, we can select $k+1$ edges such that they don't share any vertex. Whenever we select an edge, all its connected edges, can not be selected, which are at most $3n$. When we select $k$ edges, there are a few edges left. So we can select $k+1$ edges that don't share any vertex.

bruh rip tunnel vision. im goin g to DIe. also my combo writeup skills are like garbage

M GOSH. I SPENT 10+ HOURS ON THAT. WHY DO I SUCK AT COMBO SO MUCH. IT WASNT EVEN THAT HARD

Solved with Upwgs_2008 Typed on mobile

$\textbf{The answer is: \boxed{3nk}}$ First state the problem graph theoretically. let vertices be the colors of candies and each vertex has degree $\leq 2n$. and two vertices are joined iff a kid has candies of those two. Now consider the maximal matching $\mathcal{M}$of the graph. Obviously each edge outside $\mathcal{M}$ has a neighbor in $\mathcal{M}$. $\textbf{Claim:}$ each edge in $\mathcal{M}$ has at most $2n$ neighbors out side $\mathcal{M}$. $\textbf{Proof:}$ Let $ab\in \mathcal{M}$ be an edge.assume otherwise then there exist $u,v$ such that $ua,vb$ are edges as each edge had $deg\leq 2n$. but then we can remove $ab$ and add $ua,vb$ to $\mathcal{M}$. which contradicts the minimality. Then the maximum count of vertices inside $\mathcal{M}$ is $(2n)(2k)=4nk$ and outside the maximum is $(2n)(k)=2nk$. So the total is $6nk$ and by handshake lemma the maximum number of edges is $3nk$. We are done. $\textbf{Construction:}$ take $3n$ students and then give a pair of colors to the first $n$ and so on, i.e $3n$ ppl get the colors $(1,2)(2,3)(3,1)$. then make k such triangles. PS: this was a very fun problem i and a friend of mine group solved it it took us a good 5 hr but was very fun.

Reinterpret the problem using a multigraph, where each distinct color represents a vertex of degree at most $2n$, the edges represent kids, and the maximum matching contains at most $k$ edges. We claim the answer is $\boxed{3nk}$, which can be constructed with $k$ copies of a graph with three vertices and $n$ edges between each pair of vertices. Define $V$ as the vertex set of a maximum matching, and $\overline V$ as the rest of the vertices. Since $V$ is maximal, the vertices in $\overline V$ are only adjacent to vertices in $V$. For $v \in V$, define $a_v$, $b_v$ as the number of edges connected from $v$ to vertices in $\overline V$, $V$, respectively. Then \begin{align*} \text{Edges} &= \sum_{v \in V} a_v + \frac 12 \sum_{v \in V} b_v \\ &= \frac 12 \sum_{v \in V} (a_v+b_v) + \frac 12 \sum_{v \in V} a_v \\ &\leq \frac{2n \cdot 2k}{2} + \frac 12 \sum_{v \in V} a_v. \end{align*} To get our desired bound of $3nk$, it suffices to show: For an edge $uw$ in the maximal matching, we have $a_u + a_w \leq 2n$. Suppose FTSOC we have an edge $uw$ with $a_u + a_w > 2n$. Then there exist two vertices in $\overline V$, one of which has at least one edge connecting to $u$ and other has at least one edge connecting to $w$. But then we are able to replace the edge $uw$ in our maximal matching with these two edges which still satisfy the matching, contradiction. $\blacksquare$