Let $n \geq 2$ be an integer. We place $n$ points $A_{1}, \ldots, A_{n}$ on a line, then we color in red the midpoint of each segment $A_{i} A_{j}$ (with $i \neq j$), thus obtaining $N$ red points. Determine the set of values that $N$ can take.

## 2 Solution
We denote $A_{1}, \cdots, A_{n}$ as the points from left to right, and $a_{1}<$ $\cdots<a_{n}$ as their abscissas. It is clear that there are at most as many midpoints as there are segments, which is $\frac{n(n-1)}{2}$. And, $N \geq 2 n-3$ by induction. The initialization at $n=2$ is clear. For the rank $n+1$, it suffices to see that the midpoints of $\left[A_{n-1} A_{n+1}\right]$ and of $\left[A_{n} A_{n+1}\right]$ have an abscissa strictly greater than the previous ones and are distinct: $a_{i}+a_{j}<a_{n-1}+a_{n+1}<a_{n}+a_{n+1}$ for $i<j \leq n$. Therefore, $N \geq 2 n-3$.

If we choose $a_{i}=i$, the midpoints have integer or "half-integer" abscissas between $\frac{3}{2}$ and $\frac{2 n-1}{2}$, so $N \leq 2 n-1-3+1 \leq 2 n-3$. Thus, the value $2 n-3$ can be achieved. And in this case, all these integer and half-integer abscissas are reached.

Note: we will keep integer values for the $a_{i}$ in the construction to come, and thus the midpoints will be integers or "half-integers".

Next, we shift $a_{n}$ to the right by successively adding 1 until we obtain $a_{n}=2^{n}$. The set $E$ of midpoints $\left[A_{i} A_{n}\right]$, with abscissa $\frac{i+n}{2}$, is "shifted" to the right by $\frac{1}{2}$ at each step. The set $E^{\prime}$ of other midpoints are the integers and half-integers between $\frac{3}{2}$ and $\frac{2 n-3}{2}$ according to the induction above. We see that we will add one by one $n-3$ distinct midpoints by this rightward shift: the midpoints of $\left[A_{i} A_{n}\right]$ with $i \leq n-3$ were part of $E^{\prime}$, and only those. We will "remove" them one by one until they are all beyond $2^{n-1}$ when $a_{n}=2^{n}$. Then we shift $a_{n-1}$ to the right and stop at $2^{n-1}$. Similarly, we add $n-4$ new red points. And none of these midpoints coincide with those previously moved, as they are all beyond $2^{n-1}$.

By induction on $k \leq n-1$, the shift of $a_{n-k}$ to $2^{n-k}$ adds one by one $n-k$ red points. $N$ can take all values between $2 n-3$ and $2 n-3+\sum_{k=0}^{n-1}(n-3-k)=2 n-3+\frac{(n-2)(n-3)}{2}-1=\frac{n(n-1)}{2}$. This completes our proof.

## IX. Last Period

## 1 Group A

1 Wednesday, May 27 morning: graphs, Guillaume Conchon-Kerjan

## Graphs

## Introduction

The short course given here can be fruitfully expanded by reading Pierre BORNSZTEIN's polycopied "Cours - Théorie des graphes" (2003), both for the details of the proofs and the abundance of examples and exercises, which, as they age, take on value like a good wine (well, anyway).

What is a graph? Simply the data of vertices, which are connected to each other by edges (not necessarily straight). We can write it more formally as follows:

Definition. A graph $G$ is a pair $(S(G), A(G))$, where the $x \in S(G)$ are the vertices of the graph, and the elements of $A(G)$, of the form $(x, y)$ with $x, y \in S(G)$, are its edges.

More concretely, we represent it (non-uniquely) in the plane by a drawing:

![](https://cdn.mathpix.com/cropped/2024_05_10_8c44cd8b5c585c15e58bg-411.jpg?height=363&width=577&top_left_y=2303&top_left_x=585)

Example. Here, $S(G)=\{A, B, C, D, E\}$ and $A(G)=\{(A, B),(A, D),(C, E)\}$. We can imagine that these are people, connected by an edge if and only if they know each other.

We call a subgraph of a graph a part of it: we keep some vertices, and some edges that connect them. The only restriction is that we cannot keep an edge whose at least one endpoint has been removed.

A path is a sequence of adjacent edges, connecting two vertices. We speak of a cycle when the path arrives where it started. A graph is said to be connected if there is always a path between any two vertices of it.

Remarks. Let us allow ourselves a few assumptions.

- We will assume that there is a finite number of vertices, in other words, that the graphs are finite.
- We will also imply, unless otherwise stated, that the edges are undirected $((A, B)=(B, A))$ and not multiple: at most one edge can connect two vertices.

We call the degree of a vertex the number of edges that come out of it. Note that each edge contributes to the degrees of two vertices. This allows us to establish the following result:

## Lemma. Handshakes

In any graph, there is an even number of vertices of odd degree.

Proof. Indeed, the sum of the degrees of the vertices is twice the number of edges. There is therefore an even number of odd terms in this sum.

Let us phrase this differently: