수갤에 있는 조합론 문제 퍼왔어요: https://gall.dcinside.com/board/view/?id=mathematics&no=315638


1000개의 도시가 있는데, 존재하는 어떠한 두 도시의 쌍들 사이에 흙길이 있어, 흙길을 따라 임의의 두 도시 사이를 이동 가능하다고 한다. 정부가 도로들 가운데 일부를 포장하는데, 모든 도시가 홀수개의 포장도로를 가지게 할 수 있음을 증명하여라.


저는 이런 문제 보면 바로 얼어버리는데 고수님들은 일단 뭐부터 하는지가 궁금하네요.


(오히려 눈 아픈) 형식화된 버전:

집합 V⊆N를 V := { n∈N : n ＜ 1000 }으로 두자.

(1)과 (2)를 만족시키는 임의의 관계 E⊆V×V에 대하여 어떤 관계 R⊆V×V이 존재하여 (3), (4)와 (5)가 만족함을 보이시오.

1) (∀x∈V) (∀y∈V) (x E y ↔ y E x) ∧ (∀x∈V) ￢ (x E x).

2) (∀S⊆V×V) (((∀x∈V) (x S x) ∧ (∀x∈V) (∀y∈V) (∀z∈V) ((x S y ∧ y S z) → x S z) ∧ (∀x∈V) (∀y∈V) (x E y → x S y)) → S = V×V).

3) (∀x∈V) (∀y∈V) (x R y ↔ y R x) ∧ (∀x∈V) ￢ (x R x).

4) (∀x∈V) (∀y∈V) (x R y → x E y).

5) (∀x∈V) (∃k∈N) (#{ y∈V : x R y } = 2 * k + 1).

단, N = {0, 1, 2, ...}이다.