Graph Theory

Graph Theory
Prove that a graph G is m-colorable if and only if α(G□Km) ≥ n(G).
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 10Solution1. ($\Rightarrow$) If $G$ is $m$-colorable: Assume there exists a proper $m$-coloring $f : V(G) \to {1, 2, \ldots, m}$. For each color $i$, let $I_i = {v \in V(G) \mid f(v) = i}$. Each $I_i$ is an independent set in $G$. Consider the Cartesian product $G \square K_m$. The vertex set of $G \square K_m$ is:$$V(G \square K_m) ..
→2025.01.14
Graph Theory
The Turan graph $T_{n,r}$ is the compelete $r$-partite graph with $b$ partite sets of size $a+1$ and $r - b$ partite sets of size $a$, where $a = \lfloor n/r \rfloor$ and $b = n - ra$.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7Solution1. Prove that $e(T_{n,r}) = (1 - \frac{1}{r})\frac{n^2}{2} - \frac{b(r-b)}{2r}$.a. The degree of a vertex $v$ in an independent set of size $a$ is $\deg_G(v) = n - a$.- The degree of a vertex $v$ in an independent set of size $a+1$ is $\deg_G(v) = n - a - 1$.b. For independent sets of size $a$, there are $r-b$ such sets, each ..
→2025.01.14
Graph Theory
Find ordering of the vertices of G for which the greedy algorithm requires 3, and 4 colors,respectively.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 9Solution1. Let the index of colors be $\bigcirc 2. Let the ordering of vertices of$G$be$g, d, e, c, f, a, b, h$.In this order, Greedy Coloring requires 3 colors. (See the left graph below.)3. Let the ordering of vertices of$G$be$g, e, d, f, b, h, c, a$.In this order, Greedy Coloring requires 4 colors. (See the right graph below...
→2025.01.14
Graph Theory
Let $e_i(G)$ denote the number of vertices of G whose degree is strictly greater than i. Use the greedy algorithm to show that if $e_i(G) \leq i + 1$ for some i, then $\chi(G) \leq i + 1$. Find an example H that satisfies $e_4(H) \leq 5$ and compute χ(H)
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 9Solution1. Decide the order of all vertices.2. First, place all the vertices with $deg_G(v) > i$. Next, place the remaining vertices.3. By the given definition of $e_i(G)$, the number of vertices with $deg_G(v) > i$ is $e_i(G)$.By the given assumption, $e_i(G) \leq i+1$.Thus, $e_i(G)$ is at most $i+1$.4. Apply the Greedy Coloring algo..
→2025.01.14
Graph Theory
For every graph G, show that there is an ordering of the vertices of G such that the numberof required colors from Greedy Algorithm is exactly χ(G). (You should describe how togive such an order.)
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 9Solution1. Assume that the graph $G$ can be properly colored with exactly $\chi(G)$ colors. Remember that each color class forms an independent set. 2. Using this proper coloring, define the vertex order as follows: a. List all vertices in the color class corresponding to color 1. b. Next, list all vertices in the color class co..
→2025.01.14
Graph Theory
Choose two graphs and determine the chromatic numbers of them. Give your explanationfor each case.
Solution1. Figure (a)The graph in Figure (a) includes the subgraph $C_5$ (observe the outer 5 vertices).If the graph is 2-colorable, it must have an even number of vertices. However, $C_5$ has an odd number of vertices (5).Thus, $\chi(C_5) \geq 3$.Below is Figure (a):I marked the graph with 3 proper colors (1, 2, 3). It is 3-colorable.Therefore, $\chi(\text{graph (a)}) = 3$.2. Figure (b)The ..
→2025.01.14
Graph Theory
Use Menger’s Theorem to prove that κ(G) = κ′(G) for every 3-regular graph G.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 8Solution1. Since $G$ is a 3-regular graph, $\delta(G) = 3$. Thus, $\kappa(G) \leq \kappa'(G) \leq \delta(G) = 3$.2. Consider $\kappa(G) = 0$:If $G$ is disconnected, $\kappa'(G) = 0$.Thus, $\kappa(G) = \kappa'(G) = 0$.3. Consider $\kappa(G) = 1$:Let the vertex cut $S = {v_1}$.There are two components $C_1$ and $C_2$ in $G \setminus S$...
→2025.01.14
Graph Theory
Use Menger’s Theorem ($\kappa$(x, y) = $\lambda$(x, y) when $xy$ $\notin$ $E(G)$) to prove that $\alpha'(G) = \beta(G)$ when $G$ is bipartite.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 8Solution1. Suppose $G$ is a bipartite graph. We can divide $G$ into two independent and disjoint vertex sets $X$ and $Y$. 2. For $x \in X$ and $y \in Y$, add an edge ${x, y}$ to $G$ and let this new graph be $G'$. 3. In $G'$, consider: $\lambda_{G'}(x, y)$: the maximum number of internally disjoint $x, y$-paths, and $\kappa_{G'}(x..
→2025.01.14
Graph Theory
Let G be a simple graph of even order n having a set S of size k such that o(G-S) > k. Prove that G has at most $\binom{k}{2} + k(n-k) + \binom{n-2k-1}{2}$ edges, and that this bound is best possible. Use this to determine the maximum size of a simple $n$
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7Solution1. The total number of edges in $G$ can be expressed as: $$|E(G)| = e(G[S]) + |[S, \bar{S}]| + e(G[\bar{S}]),$$ where $e(G[S])$ is the number of edges within $S$, $|[S, \bar{S}]|$ is the number of edges between $S$ and $\bar{S}$, and $e(G[\bar{S}])$ is the number of edges within $\bar{S}$. 2. Since the size of $S$ i..
→2025.01.14
Graph Theory
Prove or disprove: If G is a 3-regular graph with at most two cut-edges, then G has a 1-factor.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 8ProblemProve or disprove: If $G$ is a 3-regular graph with at most two cut-edges, then ( G ) has a 1-factor.Solution1. We will use Tutte's theorem and Proposition 4.1.12: If $S$ is a set of vertices in a graph $G$, then: $$|[S, \bar{S}]| = \sum\limits_{v \in S} d(v) - 2e(G[S]),$$ where $|[S, \bar{S}]|$ represents the numbe..
→2025.01.14

• 이전
• 1
• 2
• 3
• 4
• 5
• 다음