https://arca.live/b/math/22485561?p=1

중학교 문제라고 하네요.

문제를 그래프로 치환해서 생각합시다. 

문제를 수학적으로 쪼개는 과정을 보여드리자면, 다음과 같습니다. 

어떤 국가에 50000개의 도시가 있다.  -> 50000개의 꼭짓점(=vertex)이 있다.  (꼭짓점은 유한 개, 짝수 개)

도로를 놓았다. -> edge

이 국가는 산업화 이전에 이 도시들 사이에 임의로 도로를 놓아서, 그 어떤 두 도시를 고르더라도 서로 간의 이동이 가능하게 하였다.  -> connectedness,

단, 그 어떤 두 도시 사이에도 도로를 두 개 이상 놓지 않았다 -> 두 vertex가 결정되면, 두 vertex를 잇는 edge가 유일하거나 존재하지 않음.  따라서 서로 다른 두 vertex v1, v2를 잇는 edge를 그냥 {v1, v2}라고 정의할 수 있음. 

포장 도로 -> edge들 중에서 일부를 선택. (주어진 edge들의 집합의 부분 집합 찾기.)

G=(V, E)라는 finite connected graph를 생각해 보죠.   (V는 vertex들의 집합, E는 edge들의 집합.  여기로 따지면 E는 포장 도로들의 집합, V는 도시들의 집합이죠.) 

여기서, connected graph는 walk의 존재성을 의미한다고 보죠.

즉, 한 도시에서 한 도시(두 도시가 서로 다를 필요는 없음.)를 가는 (유한 길이의) 방법이 존재하는 겁니다. 그 방법은 수학적으로 (a1, a2, .... , an) 같은 방식으로 유한 개의 vertices들로 이루어져 있고, {ai, a(i+1)}∈E (즉, G의 edge)라는 조건을 만족, a1은 시작점, an은 도착점입니다. 

그리고 path라는 것은, 위의 walk 개념에서 a1, a2, ..., an이 전부 다른 경우를 의미합니다. 

walk는 충분히 길어질 수 있고, 중간에 쓸데 없는 곳을 왔다 갔다 하면서 도착점에 갈 수 있기 때문에 여기선 그다지 써먹기 좋은 개념이 아닙니다. 그러니 path가 존재한다는 것을 증명하죠.

일단, 간단한 lemma들을 먼저 살펴 보고 갑시다. 

   lemma1 : 서로 다른 두 v1, v2∈V에 대해, v1에서 v2로 가는 path가 존재한다. 

   pf of lemma1)  G가 connected graph이니, v1에서 v2로 가는 임의의 walk W=(a1, a2, ..., an)에 대해, W가 path가 아니라면 

                    D(W)={k∈{2, ... n } | ak ∈{a1, a2, ..., a(x-1)} } 이라고 하면, D(W)가 공집합이 아니라는 것이고, D(W)에서 최솟값                         x를 잡으면, ax=ay인 y∈{1,2, ..., x-1} 가 존재,  a(y+1), a(y+2), ... , ax 를 W에서 제외해 봅시다. 

                    그러면, W' = (a1, a2, .... , ay, a(x+1), a(x+2), ..., an)=(b1, b2, ..., bm) 이 되고, W'의 길이 m은 W의 길이 n보다 작다.

                           그리고 모든 i∈{1, 2, ..., y-1}에 대해, {bi, b(i+1)}={ai, a(i+1)} ∈E 이고,   by=ay=ax, b(y+1)=a(x+1) 이므로                                 {by, b(y+1)} ∈E, 모든 j∈{y+1, ... , m}에 대해, bj=a(j-y+x), b(j+1)=a(j-y+x+1)로, {bj, b(j+1)}∈E이다. 따라서                              W'은 v1에서 v2로 가는 work이다.

                    즉, v1에서 v2로 가는, path가 아닌 임의의 walk W에 대해, W보다 길이가 더 짧은 walk가 존재한다. 

              이제 A={W | W는 v1에서 v2로 가는 G의 walk}라는 집합을 잡자. A는 공집합이 아니다. 그리고 A의 모든 원소들은 길                 이가 유한하다. 자연수의 공집합이 아닌 부분 집합에서는 언제나 최솟값이 존재하므로, A의 원소 중에서 최소 길이를                 갖는 원소 P가 존재한다.  그러면, P가 path가 아니라면, P보다 더 짧은 walk가 존재해야 하는데, 그런 walk는 존재하지                않으므로 P는 v1에서 v2로 가는 G의 path이다.

  lemma 2 : G'=(V', E')에 대해, |V'|이 짝수이면, |{v∈V' | v와 연결된 E'의 원소의 개수가 홀수}|와 |{v∈V' | v와 연결된 E'의 원소의       개수가 짝수}| 는 둘 다 짝수이다. 

  pf of lemma2)  G'의 vertex 개수 |V'|를 n개라고 하죠. 

                      그리고 모든 vertex에 대해, 각 vertex v에 대해, v에 연결된 edge의 개수가 k_v개라고 정의하죠. 

                      그러면, 다음의 식이 성립합니다. 

                      1/2∑k_v (where v∈V)   = |E| = edge의 개수.

                      그러면, ∑k_v (where v∈V) = 2|E| 로서, 언제나 짝수가 된다는 것을 알 수 있죠.

                      그러면, |V|가 짝수이므로. k_v들 중에 홀수인 것들은 짝수 개, 짝수인 것들도 짝수 개여야 합니다. 

   lemma3 : 임의의 finite graph는 G'=(V', E') 은 서로 겹치지 않는 connected graph들로 나눠진다. 

   pf of lemma3)  V'은 꼭짓점들의 집합인데, 이 꼭짓점들을 서로 겹치지 않게 분류해줄 것입니다. 기본적인 아이디어는, 한 점을             잡고, 그 점에서 출발해서 (V', E')이라는 그래프 안에서 도달 가능한 점들의 집합을 생각하면 됩니다. 이걸 모든 점에 대해서           해서 분류해주면 됩니다. 좀 더 엄밀하게 접근해 보죠.

   R={ (a, b) | a∈V', b∈V', a에서 b로 가는 (V', E')의 walk가 존재} 라고 해 봅시다. 

   그러면, R은 다음의 성질을 갖습니다. 

    모든 v∈V'에 대해, (v, v)∈R                      자기 자신에서 자기 자신으로 가는 walk가 존재하죠.

    모든 (v, w)∈R에 대해, (w, v)∈R                 v에서 w로 가는 walk가 존재하면, w에서 v로 가는 walk도 존재하죠.

    모든 (v, w)∈R , (w, x)∈R 에 대해, (v, x)∈R       v에서 w로, w에서 x로 가는 walk가 존재하면, v에서 x로 가는 walk도 존재하죠.  요약하면, R은 V'에 대한 동치류가 된다는 의미입니다. 

   이 개념에서, V'/R={ { x ∈V | (a, x)∈R } | a∈V}= {W_1, W_2, ... , W_m} 이라고 합시다. 그러면, W_1, W_2, ..., W_m은 서로 겹치      지  않고, W_1UW_2U .... U W_m = V'가 됩니다. 

   이제 꼭짓점들을 분류해줬으니, edge들을 분류해 줍시다. 

   ∀i∈{1, 2, ... , m}에 대해 E_i={e∈E' | e⊆ W_i}라고 합시다.

   그러면, E_1UE_2U...UE_m⊆E'입니다.  그리고 W_1, ... ,W_m이 서로에게 서로소였고, E'의 원소에 공집합은 없으므로, E_1,. .., E_m      도 서로에게 서로소입니다. (서로 다른 두 개의 교집합이 공집합)

   그리고 임의의 e={v, w}∈ E'에 대해, v∈W_x인 x∈{1, 2, ... ,m}이 존재하고, 그러면 (v, w)∈R, w∈ W_x, e⊆W_x, ei∈E_x이므로,  

   E'⊆E_1UE_2U...UE_m,  E'=E_1UE_2U...UE_m가 성립합니다. 

   따라서 G'은 (W_1, E_1,), (W_2, E_2), ... (W_m, E_m)이라는 각각이 connected이고, 

   W_1UW_2U .... U W_m = V' , E'=E_1UE_2U...UE_m이고, W_1~W_m은 서로소인 그래프들로 나눠질 수 있습니다. (꼭짓점이 한 개     인 그래프도 connected 입니다.)

   lemma4 : 임의의 finite connected graph G*=(V*, E*)에 대해, |V*|≥2이면, E*의 어떤 부분 집합 E'에 대해, G'=(V*, E')은                             connected graph이면서 모든 e'∈E'에 대해, (V*, E'-{e'})는 connected graph가 아니다. 

   pf of lemma4)  G*는 finite graph이므로, E*도 finite set이다. |V*|≥2이므로 E*는 공집합이 아니다. 

   E*={e1, e2, .., en}=E_0라고 하자. 

   그리고 ∀i∈{1, 2, ...., n}에 대해, E_i = { E_i-{ei}   ( (V*, E_i-{ei})가 connected graph인 경우)

                                                { E_i        ( (V*, E_i-{ei})가 connected 하지 않은 경우) 

   라고 정의하면, (V*, E_0)가 connected graph이므로 (V*, E_i)도 connected graph이고, E_i⊆E_0이다. 

   E_i의 성질을 좀 더 엄밀하게 증명하고 싶으면 간단한 수학적 귀납법으로 증명해도 된다.

   이제 G'=(V*, E_n) 이라고 하자. 그러면, G'은 connected graph이고, 모든 e'∈E_n에 대해, e'∈E*이므로 어떤 m∈{1, 2, .., n}에 

   대해 e'=em이고, 

         만약 (V*, E_n-{em})이 connected라면, E_n-{em} ⊆E_(m-1)-{em}이므로 (V*, E_n-{em})의 모든 walk는 (V*, E_(m-1)-{em})의             walk가 되고, 

         (V*, E_(m-1)-{em})은 connected graph가 되므로, E_n⊆E_m=E_(m-1)-{em}, E_n은 em을 원소로 갖지 않는다.

  따라서 (V*, E_n-{em})은 connected graph가 아니다.    

  (즉, G'은 minimal connected subgraph of G* with same vertice set of G*이다. )

이제 간단한 lemma들을 봤으니 본격적으로 들어가 보죠.  특히, lemma3는 증명 자체의 내용보다는 증명에 쓰인 테크닉이 중요합니다.

claim : G=(V, E)를 꼭짓점의 개수가 짝수 개인 finite connected graph라고 하자. 그러면, 어떤 부분 집합 E'⊆E에 대해, 모든 v∈V에 대해, |{ e∈E' | v는 e에 연결되어 있다.}|=|{e∈E' | v∈e}| 가 홀수이다.

pf of claim : 

수학적 귀납법을 써 보죠. 

base case : |V| = 2 또는 0인 경우.

꼭짓점이 0개인 경우에서는 그냥 참입니다.  (E'을 공집합으로 놓으면 됩니다.)

connected graph이고 꼭짓점이 2개인 graph는 언제나 edge가 1개이고, 각각의 꼭짓점은 1개의 edge와 연결되어 있습니다.  (E'=E라고 하면 됩니다.)

귀납법 가정  : 

//특정 양의 짝수 N에 대해, 

임의의 finite connected graph G*=(V*, E*)에 대해, |V*|가 짝수이고, |V*|＜N이면, 어떤 E*의 부분 집합 E'에 대해 {v∈V* | v에 연결된 E'의 원소의 개수가 짝수}가 공집합이 된다.

|V|=N이라고 하자.//

그러면, lemma4에 의해, E의 어떤 부분 집합 E*이 존재하여, G*=(V, E*)은 connected graph이면서 모든 e*∈E*에 대해, (V, E*-{e*})는 connected graph가 아닙니다. 

즉, G*는 minimal connected subgraph of G with same vertice set of G입니다. 

이제, W={v∈V| v와 연결된 E*의 원소의 개수가 짝수}라고 하면, lemma2에 의해, |W|는 짝수입니다. 

그리고 |W|는 0 또는 양의 정수입니다. 케이스 분류를 합시다. 

case1) |W|=0.  

그러면, E'을 E*로 놓으면 문제의 조건을 만족합니다.

case2) |W|>0. 

그러면, w를 W의 원소라고 합시다. 그리고 V_w= {v∈V-{w} | {v, w}∈E*}={a1, a2, ..., ak}라고 하고, ∀i∈{1, 2, .., k}에 대해 ei={ai, w}라고 하면, (V, E*-{ei})가 disconnected graph가 됩니다. 

 참고로, k는 양의 짝수입니다. 그러면 (V, E*-{e1, e2, ..., ek })도 disconnected graph이고, 

lemma3에 의해 (V, E*-{e1, e2, ..., ek })는 서로 겹치지 않는 connected graph들로 나눠질 겁니다.

 (V, E*-{e1, e2, ..., ek })에서 w에 연결된 꼭짓점은 없으므로 G_0=({w}, {}) 는 그런 connected graph 중 하나입니다.

이제, ∀i∈{1, 2, .., k}에 대해, V_i={v∈V |  (V, E*-{e1, e2, ..., ek }) 위에서 ai에서 v로 가는 walk가 존재.}, E_i={e∈E*-{e1, e2, ..., ek } | e⊆ V_i}, G_i=(V_i, E_i)라고 합시다. 

그러면, G_i는 connected graph입니다. 

그리고, 모든 v∈V-{w}에 대해, lemma1에 의해, G 위에서 v에서 w로 가는 path P=(x_1, x_2, ...., x_k')가 존재하고, x_(k'-1)∈V_w이며, 

∀i∈{ x | x∈{1, 2, ..., k'}, x＜k'-1}에 대해 path의 정의에 따라 x_i와 x_(i+1)은 w가 아니어야 하므로, {x_i, x_(i+1)}은 {e1, e2, ..., ek }의 원소가 아닙니다. 

        만약 어떤 i∈{ x | x∈{1, 2, ..., k'}, x≤k'-2}에 대해, x_i∈V_w이라면, 어떤 자연수 m에 대해, x_i=am≠x_(k'-1)이고,

        Pi=(x_i, x_(i+1), ..., x_(k'-1), x_k')은 am에서 w로 가는 (V, E*-{em}) 위의 path가 됩니다. 

        그러면, (V, E*-{em})가 connected graph가 되어 모순이 된다는 것을 보일 것인데, 

                   서로 다른 두 q, r∈V-{w}에 대해, lemma1에 따라 q에서 w로 가는 G 위의 path Pq=(q=q_1, q_2, ..., q_k''=w)와 

                   w에서 r로 가는 G 위의 path Pr=(w=r_1, r_2, ... , r_k''=r')가 존재합니다. 

                   그러면, ∀j∈{ x | x∈{1, 2, ..., k''}, x＜k''-1}에 대해 {q_j, q_(j+1)}은 {e1, e2, ..., ek }의 원소가 아닙니다. 

                   마찬가지로 Pr을 거꾸로 뒤집은 경로 (r_k''', r_(k'''-1), .., r_1)는 r에서 w로 G의 경로이므로 

                     ∀j∈{ x | x∈{1, 2, ..., k'''}, 1＜x＜k'''}에 대해 {r_j, r_(j+1)}은 {e1, e2, ..., ek }의 원소가 아닙니다. 

                      2-1) Pq와 Pr 모두 em을 건너지 않는 경우. 

                            Pq와 Pr은 (V, E*-{em}) 위의 path가 되므로, Pq+Pr=(q_1, q_2, ..., q_k'', r_2, r_3, ..., r_k''')은 

                           q에서 r로 가는 (V, E*-{em}) 위의 walk가 됩니다. 

                    참고로, 서로 다른 두 경로를 서로 따라 이동하다보면 한 점을 두 번 지날 수도 있으므로 path는 아닐 수 있습니다.

                     2-2) Pq가 em을 건너고 Pr은 em을 건너지 않는 경우,

                            em={q_(k''-1), q_k'} ={am, w}={x_i, w}인데, x_i에서 v_(k'-1)로 가는 (V, E*-{em}) 위의 경로 Pi가 존재하므로 

                            q에서 x_i=q_(k''-1)=am으로, am에서 w까지, w에서 r까지 이동 em을 경유하지 않고 이동 가능. 즉,

                            (q_1, q_2, ..., q_(k''-1)) + (x_i, x_(i+1), ..., x_(k'-1)) + (r_1, r_2, r_3, ..., r_k''')

                           = (q_1, q_2, ..., q_(k''-1)=x_i, x_(i+1), ..., x_(k'-1)=r_1, r_2, r_3, ..., r_k''')는 

                            q에서 r로 가는 (V, E*-{em}) 위의 walk가 됩니다.   

                      2-3) Pq가 em을 건너지 않고, Pr은 em을 건너는 경우,

                            2-2에서 r과 q를 서로 뒤바꾸면 사실상 동일합니다. 

                            em={r_2, r_1} ={am, w}={x_i, w}인데, x_i에서 v_(k'-1)로 가는 (V, E*-{em}) 위의 경로 Pi가 존재하고, 

                            q에서 w로, w에서 x_i로, x_i에서 r로 이동 em을 경유하지 않고 이동 가능. 즉,

                            (q_1, q_2, ..., q_k''=w) + (w=x_k', x_(k'-1), , x_i) + (x_i=r_2, r_3, ..., r_k''')

                            =(q_1, q_2, ..., q_k''=x_k', x_(k'-1), , x_i=r_2, r_3, ..., r_k''')는 

                            q에서 r로 가는 (V, E*-{em}) 위의 walk가 됩니다.  

                      2-4) Pq와 Pr 모두 em을 건너는 경우.

                            em={q_(k''-1), q_k'} ={x_m, w}={r_2, r_1}이므로, q_(k''-1)=x_m=r_2입니다.  

                            즉, w를 경유하기 바로 전인 x_i에서 교차해주면 됩니다.

                            (q_1, q_2, ..., q_(k''-1)=x_i)+(x_i=r_2, r_3, ..., r_k''')= (q_1, q_2, ..., q_(k''-1)=r_2, r_3, ..., r_k''')는

                            q에서 r로 가는 (V, E*-{em}) 위의 walk가 됩니다.  

               그러면, 2-1~2-4)에 의해, q에서 r로 가는 (V, E*-{em}) 위의 walk가 존재합니다.

               그리고, q에서 v_(k-1)로 가는 (V, E*-{em}) 위의 walk가 존재하고, v_(k-1)에서 w로 가는 (V, E*-{em}) 위의 경로 

                (v_(k-1), w)가 존재하므로 q에서 w로 가는 (V, E*-{em}) 위의 walk도 존재합니다.

                따라서 임의의 q∈V, r∈V-{q}에 대해, q에서 r로 가는 (V, E*-{em}) 위의 walk가 존재하므로, 

                (V, E*-{em})는 connected graph입니다.  (모순)

그러면 모든 i∈{ x | x∈{1, 2, ..., k'}, x≤k'-2}에 대해, x_i는 V_w의 원소가 아닙니다. 따라서 v∈V_m'을 만족하는 m'∈{1, 2, ..., k}이 유일하게 존재하고 v_(k'-1)=am'이며, v∈UV_j  (j=1에서 k까지) 입니다.

그러면, V=(V-{w}) UV_0 = V_0∪V_1∪....∪V_k

모든 m'∈{1, 2, ..., k}에 대해, am'∈V_m'이므로 V_m'은 공집합이 아니며, 모든 n'∈{1, 2, ..., k}-{m'}에 대해, V_m'과 V_n'은 서로소입니다. 

즉, (V, E*-{e1, e2, ..., ek })는 정확히 G_0, G_1, ..., G_k들의 connected graph로 나누어집니다. 

그리고 |V|=|V_0|+|V_1|+...+|V_k| 짝수이고, k는 짝수이고, |V_0|=1이므로,  |V_1|+...+|V_k|는 홀수입니다. 즉, |V_1|, ..., |V_k|이 모두 홀수일 수 없으므로 이 중에는 짝수가 존재해야 합니다. 

그러면, |V_p|가 양의 짝수가 되는 p∈{1, 2, ..., k}를 잡읍시다. 

이제 보일 것은, (V, E*-{ep})가 G_p와 (V-V_p, E*-{ep}-E_p)의 두 connected graph로 나뉘어짐을 보인 뒤에 각 그래프에 귀납법의 가정을 적용할 것입니다. 

 V'_p={ v∈V | ap에서 v로 가는 (V, E*-{ep}) 위의 경로가 존재.}, W'_p={ v∈V | w에서 v로 가는 (V, E*-{ep}) 위의 경로가 존재.} 라고 합시다. 

그러면, G_p=(V_p, E*-{e1, e2, ..., ek}) 위의 모든 경로는 (V, E*-{ep})의 경로이므로, V_p⊆V'_p가 성립합니다. 

그리고 임의의 i∈{1, 2, ..., k}-{p}에 대해, 임의의 v∈G_i=(V_i, E*-{e1, e2, ..., ek})에 대해 v에서 ai로 가는 G_i 위의 경로가 존재하고, G_i 위의 경로와 (ai, w)는 (V, E*-{ep}) 위의 경로이므로 

v에서 w로 가는 V, E*-{ep}) 위의 경로가 존재, v∈W'_p 가 됩니다. 그리고 w∈W'_p입니다. 

즉, (V_0UV_1U...UV_k)-V_p =V-V_p⊆W'_p가 성립합니다.

따라서 V'_p U W'_p = V=V_p U  (V-V_p)가 성립합니다. 

         이때, v∈W'_p∩V'_p인 원소가 존재하면, ap에서 v로, v에서 w로 가는 (V, E*-{ep}) 위의 경로가 각각 존재하여 

         ap에서 w로 가는 (V, E*-{ep}) 위의 walk가 존재하게 되므로 

         W'_p=V'_p=V가 되는데, 이는 곧 (V, E*-{ep})가 connected graph라는 것이므로 모순입니다. 

따라서 V'_p와 W'_p는 서로소이고, V-V_p와 V'_p도 서로소가 되므로, V'_p=  V∩V'_p=(V_p U (V-V_p ))∩ V'_p= V'_p∩V_p=V_p,

W'_p=V-V'_p=V-V_p.

따라서 (V, E*-{ep})는 G_p와 (V-V_p, E*-{ep}-E_p)라는 두 finite connected graph로 나뉘어지며,

1＜|V_p|＜N,  |V_p|는 짝수,

|V|가 짝수이므로,  |V-V_p|=|V|-|V_p|=N-|V_p| ≤N-1,  |V-V_p|는 짝수로서 두 그래프는 모두 귀납법의 가정을 만족합니다. 따라서 

어떤 E_p의 부분 집합 E''에 대해 {v∈V_p | v에 연결된 E''의 원소의 개수가 짝수}가 공집합이 됩니다.

어떤 E*-{ep}-E_p의 부분 집합 E'''에 대해 {v∈V-V_p | v에 연결된 E'''의 원소의 개수가 짝수}가 공집합이 됩니다.

이제, E'=E''∪E'''이라고 하자.  E'⊆E*-{ep}⊆E이고, E''∩E'''은 공집합이고, 임의의 E''의 원소 e''과 임의의 E'''의 e'''에 대해, e''∈ E_p, e''' ∈E*-{ep}-E_p 이므로, e''∩e'''도 공집합입니다. 

그러면, 모든 v∈V_p에 대해,   모든 e∈E'''에 대해, e⊆V-V_p,  e는 v를 원소로 갖지 않으므로

{e∈E'|v∈e}={e∈E''|v∈e}∪{e∈E'''|v∈e} = {e∈E''|v∈e}이 되므로, |{e∈E'|v∈e}|는 홀수입니다. 

그리고 모든 v∈V-V_p에 대해, 모든 e∈E''에 대해, e⊆V_p,  e는 v를 원소로 갖지 않으므로

{e∈E'|v∈e}={e∈E''|v∈e}∪{e∈E'''|v∈e} = {e∈E'''|v∈e}이 되므로, |{e∈E'|v∈e}|는 홀수입니다. 

따라서 모든 v∈V에 대해, |{e∈E'|v∈e}|는 홀수입니다.

즉, {v∈V| v와 연결된 E'의 원소의 개수가 짝수}는 공집합입니다. 

case 1과 case 2에 의해, 어떤 E의 부분 집합 E'에 대해 {v∈V* | v에 연결된 E'의 원소의 개수가 짝수}가 공집합이 됩니다.

이때 G를 vertice 개수가 N개인 임의의 finite connected graph로 설정했습니다.

따라서 임의의 finite connected graph G*=(V*, E*)에 대해, |V*|가 짝수이고, |V*|＜N+2이면, 어떤 E*의 부분 집합 E'에 대해 {v∈V* | v에 연결된 E'의 원소의 개수가 짝수}가 공집합이 됩니다. 

그러면 수학적 귀납법에 의해,

모든 양의 짝수 N에 대해, finite connected graph G*=(V*, E*)에 대해, |V*|가 짝수이고, |V*|＜N이면, 어떤 E*의 부분 집합 E'에 대해 {v∈V* | v에 연결된 E'의 원소의 개수가 짝수}가 공집합이 됩니다.

그러면, 

|V|가 짝수인 임의의 finite connected graph G=(V, E)에 대해, |V|+2는 짝수이고, |V|＜|V|+2이므로 어떤 E*의 부분 집합 E'에 대해 {v∈V* | v에 연결된 E'의 원소의 개수가 짝수}가 공집합이 됩니다.

이로써 도시 개수가 5000개로 짝수이므로, 모든 도시에 홀수개의 포장도로가 연결되도록 할 수 있다는 것은 가능하고 이를 증명했습니다.