이것저것 공부방
Let F be a maximal forest of G. Show that: e(F)=n(G)−c(G), where e, n, and c are the number of edges, vertices, and compo-nents, respectively.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5Solution1. G has c(G) components. Each component H of G is connected and contains a spanning tree F∩H, as shown in part (a).2. A spanning tree with k vertices has exactly k−1 edges, since a tree with k vertices has k−1 edges by definition.3. Therefore, for each component H, if H has n(H) vertices, the span..
Let F be a maximal forest of G. Show that: (a) For every component H of G, F ∩ H is a spanning tree of H
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5 Solution1. A component H of G is a connected subgraph of G. Thus, H is connected by definition. F is a maximal forest of G, meaning that F is an acyclic subgraph of G and spans all components of G. 2. Since F is a forest, it contains no cycles. Thus, F∩H, as a subgraph of F, must also be acyclic. 3. $F..
What is the minumum number of cycles in graphs with n vertices and m edges?
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5Solution1. Suppose that there is a graph with n vertices and no edges. 2. As we add edges to the graph, we need to determine whether each new edge creates a cycle. A cycle is formed when there is already a path between the two vertices before the edge is added. 3. At the beginning, there are n disconnected vertices. By adding $n..
Let T be a nontrivial tree. Determine the minimum possible number of maximal indepen-dent sets in T . Determine all the possible structure of T achieving the minimum number.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5 Solution1. In a tree, there are leaf vertices and non-leaf vertices. If we take a maximal independent set that includes a leaf vertex, we can also construct a different maximal independent set that excludes that leaf and includes its neighbor instead. 2. Thus, there are always at least two distinct maximal independent sets in any t..
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 \in V(G). Hence, conclude that G is regular.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4 Solution1. Choose any vertex x in G. x has d(x) neighbors, and let them be v_1, v_2, \dots, v_{d(x)}, where d(x) is the degree of x. 2. Since G does not have triangles, there are no edges between v_1, v_2, \dots, v_{d(x)}. 3. The number of vertices non-adjacent to x is n - d(x) - 1. This is calculated as: (T..
Prove that the number of simple Eulerian graphs with vertex set \{1, 2, \dots, n\} is 2^{\binom{n-1}{2}}.
Solution1. I will define two sets of graphs:G_{n-1}: The set of simple graphs with vertex set {1,2,\dots,n-1}.E_n: The set of Eulerian graphs with vertex set {1,2,\dots,n}.2. I will show that the sizes of these two sets are the same by establishing a bijection between G_{n-1} and E_n.3. Check Injectivity:i. Given G \in G_{n-1}, construct a graph E \in E_n by adding the n-th ver..
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
Suppose that every vertex of a loopless graph G has degree at least 3.Prove that G has a cycle of even length.
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 3Solution(i). Let P = (x_0, x_1, \dots, x_k) be a longest path in G. Vertices x_0 and x_k are the endpoints of P.(ii). Since every vertex in G has degree at least 3, x_0, being one of the endpoints of P, must have at least two neighbors other than x_1, which is already on the path. These neighbors must be other verti..