Dissimilar Terms

Relevant wiki: Eulerian Path

Consider a graph with 4 vertices, $A, B, C, D$ . We are looking for the minimum number of edges with which we can draw its complete graph starting from $A$ , under the condition that there must exist a Euler Path along the graph. We can see that we need a minimum of $7$ edges to do this, since the complete graph requires 6 edges, and if 6 edges were to be made, all vertices would be of an odd degree, which makes a Euler path impossible. With 7 edges we can do it, just draw the complete graph and connect $A$ to $B$ .

We can see that this condition is similar to the one above. One edge represents one $\neq$ sign, one vertex represents one variable, and we need to make all variables not equal to each other, i.e. we must complete the edges of the graph. A Euler path along the graph is needed, since we need to start, WLOG, from $A$ and end up with some variable, and since all the variables must not be made equal in one line, we need to have a Euler path which represents the order the variables appear in in the inequality.

Suppose we are trying to say " $a_1,a_2,...,a_n$ are distinct". Consider the complete graph $K_n$ , where the vertices are the numbers $a_1,a_2,...,a_n$ , and an edge between two numbers $a,b$ is represented by the expression $a \neq b$ .

We need a path on $K_n$ which contains each edge (so that every pair of numbers are made distinct) which is as short as possible. If $K_n$ possesses a Eulerian path, then this will certainly have shortest length. If a Eulerian path does not exist, we will need to go over some edges more than once to be able to cover all edges. Put another way, we may need to add extra edges to the graph (so that some pairs of vertices are joined by two or more edges) in such a way that we can find a Eulerian path.

If we consider the complete graph $K_n$ with $n$ vertices, then each vertex has $n-1$ edges attached to it.

If $n$ is odd, then $n-1$ is even, and so every vertex of $K_n$ has an even number of edges attached to it. Thus a Eulerian cycle is possible on this graph. In this case, it is possible to express " $a_1,a_2,...,a_n$ are distinct" using $\binom{n}{2}$ symbols.

If $n$ is even, then every vertex of $K_n$ has an odd number of edges attached to it. For $n \ge 4$ , this means that no Eulerian path is possible. We need to add the smallest number of edges to the graph until we have at most $2$ vertices with an odd number of edges attached, so that a Eulerian path is then possible. The parity of the "number of attached edges" has thus to be modified for $n-2$ vertices. Since $K_n$ is complete, we can do this two vertices at a time. Choose any $n-2$ vertices, and find $\tfrac12(n-2)$ edges which join these vertices up in pairs. Add an edge parallel to each of these edges. The result is a multigraph with $\binom{n}{2} + \tfrac12(n-2) = \tfrac12(n^2-2)$ edges which possesses a Eulerian path. Since $m$ edges will adjust the parity of the "number of attached edges" for at most $2m$ vertices, it is clear that $\tfrac12(n-2)$ is the smallest number of edges that can be added so as to perform the necessary parity swaps Thus, in this case, the least number of symbols is $\tfrac12(n^2-2)$ . Note that this expression also gives the correct answer of $1$ when $n=2$ .

The number of symbols is thus $\tfrac12(n^2-n)$ if $n$ is odd and $\tfrac12(n^2-2)$ if $n$ is even. This makes the answer to this problem $\boxed{7}$ .