그래프이론 (Graph Theory) 문제풀이 하겠습니다. 이번에 풀 문제는 “Let W be a closed walk in a graph G. Let H be the subgraph of G consisting of edges used an odd number of times in W. Prove or disprove: The degree of v in H, deg_H(v), is even for every v ∈ V (G).” 입니다.
그래프이론 (Graph Theory) 문제풀이
우리가 풀고자 하는 문제는 아래와 같습니다.
Let W be a closed walk in a graph G. Let H be the subgraph of G consisting of edges used an odd number of times in W. Prove or disprove: The degree of v in H , deg_H(v), is even for every v ∈ V (G).
pf) W를 하나의 graph 로써 생각해보겠습니다. 그리고 v가 W를 구성하는 vertex중 하나라고 해봅시다. v와 incident한 W상의 모든 edge를 e_1,e_2,...,e_K 이라고 표시합니다. W를 구성하기 위해 각각의 edge e_i 가 사용된 횟수를 m_i 라고 합시다. closed walk 이므로 한 vertex에 edge가 지나간 횟수의 총합은 짝수가 됩니다.
\sum_{i=1}^K m_i \text{ 는 짝수}여기서 m_i 가 짝수 or 홀수인 경우로 나눠생각하면 아래와 같이 되는데요.
\sum_{i=1}^K m_i = \sum_{i: m_i:even} m_i +\sum_{i: m_i:odd} m_i \text{ 는 짝수}이렇게 되면 m_i 가 odd인 i 의 갯수는 짝수개여야 합니다.
H는 홀수번 사용된 edge들로만 구성된 graph인데 , 각 vertex에 대하여 홀수번 사용된 edge의 갯수는 짝수개이므로 deg_H(v) : 짝수 \text{ for all v in V(H)}가 성립합니다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 4 문제