그래프이론(Graph Theory)문제풀이 해보겠습니다. 오늘 풀어볼 문제는 아래와 같습니다.
Find all simple graphs with n vertices having no isolated vertex and no induced subgraph with exactly two edges.
isolated vertex가 없고 두개의 edge만으로 구성된 induced subgraph 가 없는 그래프는 어떤 그래프일까요? 이번 글에서는 그 그래프를 찾아보겠습니다.
도움이 될만한 글
- [그래프이론(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)문제 풀이 시작
문제를 다시한번 쓰도록 하겠습니다.
Find all simple graphs with n vertices having no isolated vertex and no induced subgraph with exactly two edges.
u,v 를 서로 다른 두개의 vertex라고 합시다. isolated vertex가 없어야 하므로 u 와 adjacent한 u_1 과 v 와 adjacent한 v_1 가 존재합니다. 여기서 경우를 나눌 수 있습니다.
- u_1 = v_1 인 경우
G[u,v,u_1] 가 edge 두개로만 구성이 되지 않기 위해서는 edge uv 가 존재해야 한다. - u_1 \neq v_1 인 경우
여기서 uv edge가 존재 하지 않는다고 하자. G[u,v,u_1,v_1] 이 두개의 edge만 갖는 그래프가 되지 않기 위해서는 uv_1 혹은 vu_1 혹은 u_1v_1 가 존재해야 한다. 만약에 u_1v_1 가 존재한다고 가정하자. 그러면 G[u, u_1, v_1] 가 세개 이상의 edge를 갖기 위해서는 uv_1 혹은 vu_1가 존재해야 한다. uv_1 가 있다고 가정하면 G[u,v_1,v] 가 세개 이상의 edge를 갖기 위해서는 uv 가 존재해야 한다. uv_1 혹은 vu_1 가 존재하는 경우에도 비슷하게 uv 가 존재해야 한다. 따라서 uv 가 존재한다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 2의 Homework Problems 중 (2)번 문제