Graph Theory
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,..
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..
Prufer code에 대하여
u는 독일어 움라우트 표기해야한다.prufer code는 트리구조를 인코딩하는 방법으로 n개 정점을 가진 트리를 n-2개 정수로 표현한다.트리로부터 프뤼퍼코드를 생성하거나 프뤼버코드로부터 트리를 생성하는 예제는 2024 그래프이론 퀴즈와 중간고사 모두에서 출제되었으므로 후배님들은 확인해보길바란다. 그냥 공부했던 내용을 기록하기 위해 붙여둔다.
Prove or disprove: Every tree T has at least $∆(T)$ leaves.
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4Solution1. Let $v$ be a vertex in $T$ with degree $\Delta(T)$, where $d(v) = \Delta(T)$. That is, $d(v)$ is the degree of vertex $v$.2. $v$ has adjacent vertices $w_1, w_2, \dots, w_{d(v)}$. That is, there exist edges $vw_i$ incident to $v$ for $1 \leq i \leq d(v)$.3. Now, for every edge $vw_i$ incident to $v$, take a longest path st..
Prove or disprove: If G is an n-vertex simple graph with maximum degree ⌈n/2⌉ andminimum degree ⌊n/2⌋ − 1, then G is connected.
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4 Solution1. Let $C_u$ be a connected component of $G$ that contains the vertex $u$ with the maximum degree, and $C_v$ be a connected component of $G$ that contains the vertex $v$ with the minimum degree.2. I will identify the contradiction that arises when $C_u$ and $C_v$ are disjoint.3. $d(u)$ is $\lceil n/2 \rceil$, where $d(u)$ is..
Let T be a tree with average degree d. In terms of d, determine $n(T)$.
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4 Solution1. Since a tree is a connected graph with no cycles, $|E_T| = n(T) - 1$, where $|E_T|$ is the number of edges in $T$. 2. The average degree $d$ is: $$ d = \frac{\sum\limits_{v \in V(T)} d(v)}{n(T)}, $$ where $d(v)$ is the degree of vertex $v$, and $V(T)$ is the vertex set of $T$. 3. In a graph, the sum of the degre..
Prove or disprove: Every graph with fewer edges than vertices has a component that is a tree.
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4Solution1. Let's consider a graph $G$ such that $|E_G| 2. Suppose that $G$ has connected components $G_1, G_2, \dots, G_k$. Each $G_i$ is a connected subgraph. If $G_i$ is not a tree, then $G_i$ must have a cycle.3. A key property of a tree is that $|E| = |V| - 1$. To add a cycle to a tree, we need at least one additional edge. Thus..
Which of the following are graphic sequences? Provide a construction.
가장 큰 차수의 정점에서 정점을 하나 제거하고, 차수를 줄여가는 식으로 그래프를 단순화하고 다시 복구해가는식으로 확인할 수 있음.e.g. 5,5,5,3,2,2,1,1-> (5x), 4,4,2,1,1,1,1-> (5x), (4x), 3,1,0,0,1,1 -> (sort) 3,1,1,1,0,0 -> 이 정도했으면 그려짐. 여기서부터 정점을 하나씩 채워서 복구하면됨. 1. 5,5,4,3,2,2,2,1 2. 5,5,5,3,2,2,1,1 3. 5,5,4,4,2,2,1,1
Use induction to prove that if a graph does not have an odd cycle thenit is bipartite. , Comment: You should first choose which parameter thatyou will apply induction on - number of vertices or number of edges.
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 2SolutionP(n): A graph with $n$ vertices and no odd cycles is bipartite.(i). Base step:- For $n = 1$, a graph with a single vertex is trivially bipartite.- For $n = 2$, a graph with two vertices cannot have an odd cycle and is bipartite.(ii). Inductive hypothesis:Assume $P(k)$ is true for some positive integer $k$.That is, any graph w..