그래프이론 (Graph Theory) 문제를 풀려고 합니다. 이번에 풀려고 하는 문제는 “What is the minimum number of edges of an n-vertex graph with diam(G) = 2 and ∆(G) = n−2?” 입니다. maximum degree 가 n-2 이고 diameter 가 2 인 graph 는 몇개의 edge를 갖냐고 물어보는 문제입니다.
그래프이론 (Graph Theory) 문제 풀이
풀려고 하는 문제를 다시 recap 해보겠습니다.
What is the minimum number of edges of an n-vertex graph with diam(G) = 2 and ∆(G) = n−2?
풀이)
G 를 n 개의 vertex를 갖고 diam(G) =2 이고 \Delta(G) =n- 2 인 graph 라고 하자.
v \in V(G) 를 deg_G(v) = \Delta(G) = n-2 만족하는 vertex 라고 하자.
n-2 개의 vertices 가 v에 adjacent 할 것이고, 이 adjacent vertices 를 v_1,v_2,...,v_{n-2} 라고 표시하자.
n(G) = n 이므로 u \notin \{ v,v_1,...,v_{n-2}\} 인 vertex u 가 존재할것이고 u 는 v 와 adjacent 하지 않는다.
diam(G) < \infty 이므로 길이가 2 인 uv path 가 존재한다.
그리고 이 path 위에는 v_i 중에 하나가 있을 것이다.
이렇다는 것은 결국엔 G 는 connected라는 얘기이다.
각각의 i 마다 v_i , u 를 잇는 path 가 있다.
여기서 경우가 두가지로 나뉜다.
Edge v_i u 가 존재하는 경우가 있고, edge v_i u 가 존재하지 않는 경우가 있다.
v_{1},...,v_{k} 는 u 와 adjacent 하고 v_{k+1} ,...,v_{n-2} 는 u 와 adjacent 하지 않다고 하자.
길이가 2이하인 u v_j (j=k+1,...,n-2) - path 가 존재하기 위해서는 각각의 j=k+1,...,n-2 마다 i=1,2,...,k 가 존재하여 v_jv_i 가 있어야 한다. 즉 j=k+1,...,n-2 마다 edge가 하나씩 추가 된다.
이를 종합하면 v 와 adjacent 한 vertex는 추가적으로 적어도 한개씩 edge가 필요하다.
따라서 최소 2n-4개의 edge가 있다.
참고할만한 글:
- [그래프이론(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.
- [그래프이론(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.
- [그래프이론 (Graph Theory) 문제풀이] Let T be an n-vertex tree having one vertex of each degree i with 2≤i≤k; the remaining n-k+1 vertices are leaves. Determine n in terms of k.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 4 문제