Every connected component have to contain cycle of odd length (prove it).
Find such a cycle and solve.

Proof that a system of linear equation has a unique solution if the corresponding cycle is of an odd length.

system of LE
x1 + x2 = y1
x2 + x3 = y2
...
x_{n-1} + x_n = y_{n - 1}
x1 + x_n = y_n

Is written in matrix form (i'll skip the last column)

1 1 0     ... 0
0 1 1 0   ... 0
0 0 1 1 0 ... 0
      .
      .
      .
0     ... 0 1 1
1 0    ...  0 1

It's determinant can be computed as follows
det(
  1 1   .. 0
  0 1 1 .. 0
      .
  0 0 .0 1 1
  0 ...  0 1
)
 +-(!!!)
det (
  1 0   .. 0
  1 1 0 .. 0
      .
      .   1 0
  0 ... 0 1 1
)


I took entries (1, 1) and (n, 1) to form these two. The sign (+-) depends on dimention and is equal to (-1)^(n + 1).

The two determinans are equal as the first one is equal to
1 1
0 1
which can be seen if you keep choosing entry (n, n) to form determinant

and the second one is equal to
1 0
1 1
keep choosing (1, 1)

So, the determinant of initial matrix is equal to 2 if the number of variables odd which means the system has a unique solution. The system can't have one in the case of zero determinant which is when the number of variables is even.

Edited by author 01.09.2018 17:02