Graph Theory
Prove that $κ(G) = δ(G)$ if G is simple and $δ(G) ≥ n(G)−2$. Prove that this is best possible for each n ≥ 4 by constructing a simple n-vertex graph with minimum degree n − 3 and connectivity less than n − 3.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7아래를 참고해서 작성한 풀이인데, 풀이가 조금 찝찝하다. 조교는 한두장 분량의 원래 매우 긴 풀이를 기대했다고 한다. 다른 괜찮은 풀이를 생각해보는게 좋겠다.https://seongqjini.com/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%B4%EB%A1%A0-graph-theory-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-prove-that-%CE%BAg-%CE%B4g-if-g-is-simple-and-%CE%B4g-%E2%89%A5-ng-%E2%88%92-2-prove-that/Solution1. Since $ \delta(G) \geq n(G) ..
For each n ∈ N, find an n-vertex graph such that $κ′(G) > κ(G)$.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7Solution1. If the graph is initially disconnected, $\kappa'(G) = 0$ . Thus, $\kappa(G) = \kappa'(G) = 0$. Therefore, we will only consider connected graphs.2. For , n = 1 :$ \kappa(G) = \kappa'(G) = 0 $ is trivial.3. For , n = 2 :The path graph ,$P_2$ is the only connected graph, and $\kappa(G) = \kappa'(G) = 1$ is trivial.4. For ,..
Draw the Cartisian product G□H, where G = K2,3 and H = K3.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7SolutionLet ( G ) be a bipartite graph, where the vertex sets are divided into two independent sets: $$ U = \{00, 01\}, \quad V = \{10, 11, 12\}. $$ Let ( H ) be a graph with vertex set: $$ V(H) = \{20, 21, 22\}. $$ The vertex set of ( G \square H ) is the Cartesian product of the vertex sets of ( G ) and ( H ):$$V(G \square H) = {(u,..
For each even n ≥ 16, construct a 3-regular simple graph with n vertices having no 1-factor.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 6Solution아래 풀이는 일반화된 풀이라기엔 부족한 감이 있다. 필자는 연결그래프만을 상상했기에 이런 풀이를 작성했으나, n=16, n=18 케이스에 K4를 추가해가는식으로 그래프를 구성하면 일반화된 풀이를 구성할 수 있다. The above figure shows a 3-regular graph (( n = 16 )) having no 1-factor, as demonstrated in Problem 5 using Tutte's theorem.Using the same definitions of ( v^* ) and ( G_i ) from Problem 5, let the subgraphs ..
For each k > 1, construct a k-regular simple graph having no 1-factor.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 6Solution아래 풀이엔 논리적 오류는 없으나, 아래에 그려둔 k=3, k=5 예시에 K4를 추가하는 방식으로 그래프를 구성해보면 더 쉽게 표현할 수 있다. 규칙성을 찾아보고 예시의 두 그래프를 각각 G1, G2로 정의하고, Union 기호를 이용해 K4를 몇개 추가하면 조건을 완성시킬 수 있을지 검토해보면된다. We will consider two cases:Case 1: $k$ is evenImagine the complete graph $K_{k+1}$.This is a $k$-regular graph with $k+1$ vertices.Since $K_{k+1}$ has an odd..
Exhibit a maximum matching in the graph below, and use various results that we learned so far to give a short proof that it is a maximum matching.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 6SolutionFor the given matching $M$, $|M| = 8$.In $M$, there is no augmenting path.We will prove that if a matching $M$ has no augmenting path, then $M$ is a maximum matching.Proof:1. Define a matching $M$ with no augmenting path.2. Assume, for contradiction, that $M$ is not a maximum matching.That is, there exists a larger matching $M..
Recover the corresponding tree with Pr¨ufer code (1, 3, 5, 7, 6, 1, 6, 4).
Length of prufer code is 8. Thus tree have 10 vertices. I defined set of degree of each vertices D. Every vertex initially has a degree of 1, and the degree of each vertex thatappears in the prufer code increases by the number of times it appears. Thus, the degreeset can be defined as D = (3, 1, 2, 2, 2, 3, 2, 1, 1, 1). From the prufer code and D, tree canbe constructed through the following pro..
Assign integer weights to the edges of Kn. Prove that the total weight on every cycle iseven iff the total weight on every triangle is even.
Solution1. Sufficient Condition: A triangle is a 3-cycle. Thus, if the total weight of every cycle is even, then the total weight of every triangle is also even. 2. Necessary Condition: We will use mathematical induction to prove this. Steps*: Base Case: For cycles of length 3 (i.e., triangles), we know by assumption that the total weight of every triangle is even. Inductive Hypothesis: ..
Determine which trees have Pr¨ufer codes that (a) contain only one value, (b) containexactly two values, or (c) have distinct values in all positions.
Solution1. Prufer code contains only one value Let the Prufer code $P = [k, k, \dots, k]$. Steps*: Number of vertices: The Prufer code has a length of $n-2$, so the tree has $n$ vertices. These vertices are ${1, 2, \dots, n}$. Decoding the Prufer code: In each step of the decoding process, the smallest leaf is selected and is made adjacent to the vertex corresponding to the first value in ..
Prufer code에 대하여
u는 독일어 움라우트 표기해야한다.prufer code는 트리구조를 인코딩하는 방법으로 n개 정점을 가진 트리를 n-2개 정수로 표현한다.트리로부터 프뤼퍼코드를 생성하거나 프뤼버코드로부터 트리를 생성하는 예제는 2024 그래프이론 퀴즈와 중간고사 모두에서 출제되었으므로 후배님들은 확인해보길바란다. 그냥 공부했던 내용을 기록하기 위해 붙여둔다.