Graph Theory
Show konig thm implies Hall’s thm
교수님께서 몇번 강조를 하셔서 증명은 해봤는데, 2024 기준 시험이나 퀴즈에 출제된 바는 없습니다. SolutionHall's Theorem:For a bipartite graph $G = (X, Y, E)$, a perfect matching exists if and only if the following condition holds:$$\forall S \subseteq X, |N(S)| \geq |S|.$$ We need to show that $\alpha'(G) = \beta(G)$ for every bipartite $G$ implies Hall's theorem. Proof: Suppose the graph $G$ satisfies the condition of Hall's theor..
For all positive integers r and d that satisfy r ≤ d ≤ 2r, construct a simple graphwith radius r and diameter d.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5 Solution(c) Construct a simple graph with radius $r$ and diameter $d$Construction: Consider the cycle $C_{2r}$ defined on $V = {0, 1, 2, \dots, 2r-1}$. In this case, we have:$$\text{rad}(C_{2r}) = r.$$ When $d = r$, the graph satisfies:$$\text{diam}(C_{2r}) = \text{rad}(C_{2r}) = r.$$ Now assume $2r \geq d > r$. Define a path $..
Use part (a) to prove that diam(G) ≤ 2rad(G) for every graph G.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5풀이(a)는 삼각부등식. 이전 풀이 참고.Proof: If there is no path $a \dots b$ or path $b \dots c$, then $d(a, b)$ or $d(b, c) = \infty$, so the inequality is trivially satisfied. Otherwise, there exists a path $a \dots b$ of length $d(a, b)$ and a path $b \dots c$ of length $d(b, c)$. We may compose these two paths to form a longer walk $a \dots b ..
(a) Prove that the distance function $d(u, v)$ on a pair of vertices of a graph satisfies the triangle inequality: $$d(u, v) + d(v, w) \geq d(u, w).$$
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5풀이1. The distance $d(u, v)$ between two vertices $u$ and $v$ is the length of the shortest path connecting $u$ and $v$. 2. Suppose $d(u, v) + d(v, w) By definition, $d(u, v)$ is the length of the shortest path from $u$ to $v$, and $d(v, w)$ is the length of the shortest path from $v$ to $w$. However, $d(u, w)$ is the length of the s..
Let $T$ and $T'$ be two spanning trees of a connected graph $G$. For $e \in E(T) - E(T')$, prove that there is an edge $e' \in E(T') - E(T)$ such that $T' + e - e'$ and $T - e + e'$ are both spanning trees of $G$.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5Solution1. Consider an edge $e \in E(T) - E(T')$. Since $e$ is not in $T'$, adding $e$ to $T'$ results in the graph $T' + e$.Because $T'$ is a spanning tree, it already spans all vertices of $G$.This means there is a path in $T'$ between any two vertices. Adding $e$, which is incident to two vertices already connected by a path in $T'..
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 \cap 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 \cap 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..