그래프이론 (Graph Theory) 문제풀이를 해보겠습니다. 제가 오늘 소개해 드릴 문제는 Use induction on n(G) to prove that every nontrivial loopless graph G has a bipartite subgraph H such that H has more than e(G)/2 edges. 입니다. loopless graph G는 edge갯수가 e(G)/2 개 이상안 bipartite subgraph H를 갖는 다는 얘기인데요. 한번 풀어보겠습니다.
그래프이론 (Graph Theory) 문제풀이
문제를 다시 써보면 아래와 같습니다.
Use induction on n(G) to prove that every nontrivial loopless graph G has a bipartite
subgraph H such that H has more than e(G)/2 edges.
저는 이 문제를 귀납법을 이용해서 풀것입니다. 귀납법을 이용해서 풀기 위해서는 statement 를 정의해야겠죠. 제가 증명하고 싶은 statement는 아래와 같습니다.
P(n): n(G)=n인 nontrival loopless graph G 는 edge의 갯수가 e(G)/2 개보다 많이 갖고 있는 bipartite subgraph H 를 갖고 있다.
이것을 이제 풀어보겠습니다.
n=1 일 때 자명하죠.
n=2 일 땐 G자체가 bipartite graph 입니다.
어떤 자연수 n에 대하여 P(n)이 true 라고 가정합니다. 그리고 G를 n(G)=n+1 인 loopless nontrival graph 라고 가정합시다. G의 vertex 중 deg_G(v) = \Delta(G) 를 만족하는 v를 선택하고 induced subgraph H=G-v 를 생각합시다. e(H) = e(G)- \Delta(G) 임을 알 수 있습니다. 귀납적인 가정에 의해 H에는 bipartite subgraph I가 존재하고 e(I) ≥ e(H)/2 = (e(G) -Δ(G))/2입니다. 여기서 Bipartition을 A,B라하고 A ∪ B = V(G) 라고 가정할 수 있습니다. N_G(v) 를 생각해보겠습니다. |N_G(v) \cup A | \geq \Delta(G)/2 이거나 |N_G(v) \cup B | \geq \Delta(G)/2 를 만족합니다. |N_G(v) \cup A | \geq \Delta(G)/2 가정해봅시다. C = B \cup \{v \} 라 하고 v 와 A 사이의 vertex를 다 이어봅시다. 그러면 A,C 를 bipartiton 으로 하는 graph 의 edge의 갯수는 e(H) + \Delta(G)/2 =e(G) /2 보다 크거나 같습니다.
참고할만한 글:
- [그래프이론(Graph Theory)] Deleting a vertex of degree ∆(G) cannot increase the average degree.
- [그래프이론(Graph Theory) 문제풀이] Prove or disprove: K9 decomposes into copies of C9.
- [그래프이론(Graph Theory)] Use induction to prove that if a graph does not have an odd cycle then it is bipartite.
- [그래프이론(Grpah Theory)] Prove that the Petersen graph has no cycle of length 7.
- [그래프이론(Graph Theory) 문제풀이] Find all simple graphs with n vertices having no isolated vertex and no induced subgraph with exactly two edges.
- [그래프이론(Graph Theory) 문제풀이]Let P and Q be be paths of maximum length in a connected graph G. Prove that P and Q have a common vertex.
- [그래프이론 문제풀이] Let u and v be adjacent vertices in a simple graph G. Prove that uv belongs to at least d(u) + d(v) − n(G) triangles in G.
- [그래프 이론(Graph Theory)-1] k-set과 k-subset
- [그래프이론(Graph Theory) 문제풀이] Deleting a vertex of degree δ(G) cannot reduce the average degree.
- [그래프이론(Graph Theory) 문제풀이] Prove or disprove: Every tree T has at least ∆(T) leaves.
- [그래프이론 (Graph Theory) 문제풀이] Prove that the number of simple Eulerian graphs with vertex set {1, 2, · · · , n} is 2 ( n−1 2 ).
- [그래프이론 (Graph Theory) 문제풀이] Let G be a triangle-free simple n-vertex graph such that every pair of non-adjacent vertices has exactly two common neighbors. Prove that n(G) = 1 + \binom{d(x)+1}{2} where x ∈ V (G). Hence, conclude that G is regular.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 3 문제