Graph Theory
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..
Prove that a graph G is bipartite iff every subgraph H of G has anindependent set consisting of at least half of $V(H)$.
문제출처광주과학기술원-GIST- 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 3SolutionI will show that both directions are true.Necessary condition:If $G$ is bipartite, then every subgraph $H$ of $G$ has an independent set containing at least half of the vertices in $V(H)$.Since $G$ is bipartite, the vertex set $V(G)$ can be divided into two independent sets $A$ and $B$. The subgraph $H$ must have its vertices..
How many simple graphs on n vertices with vertex degrees all even?
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 3SolutionDefine the finite fieldDefine the finite field $F_2$ (with elements 0 and 1). In $F_2$, addition follows modulo 2 arithmetic, meaning $1 + 1 = 0$.Graph setupThe vertex set $V = \{v_1, v_2, \dots, v_n\}$ consists of $n$ vertices.The edge set $E = \{e_1, e_2, \dots, e_m\}$ is the set of all possible edges. The number of edges i..
Prove or disprove: K9 decomposes into copies of C9.
K9의 엣지 개수는 9*(8/2)=36개이고, C9의 엣지개수는 9개이니, 36/9=4로 나누어 떨어져 이론적으로는 4개의 C9 copy로 분해되는게 가능함. 주의할건 이걸로 증명을 마쳐선 안됨. 그 존재성까지 증명해야 증명이 마무리되며, 이는 실제로 보여줌으로써 해결할 수 있음. 본인은 시계방향으로 9개 정점을 0부터 8까지 라벨링하고, 4개의 다른 경로를 가진 C9을 구성함으로써 증명을 해결하였음. 예를 들어,0-1-2-3-4-5-6-7-8-0 으로 1개 발견, 0-2-4-6-8-1-3-5-7-0으로 2개 발견,...이렇게 4개를 찾아보길 바람.