문제출처 - 광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 2
Solution
(i). Since $u$ and $v$ are adjacent, $uv$ is an edge in $G$.
(ii). The number of triangles containing $uv$ is the same as the size of the intersection of $N(u)$ and $N(v)$. $N$ means neighbor.
(iii). For example, if $N(u) = \{v, w_1, w_2, w_3\}$ and $N(v) = \{u, w_1, w_2\}$, then:
$$
N(u) \cap N(v) = \{w_1, w_2\}.
$$
Thus, the triangles containing edge $uv$ are $u-v-w_1-u$ and $u-w_2-v-u$.
This is the same as the size of $N(u) \cap N(v)$, which is 2.
(iv). The union of neighbors can be expressed as:
$$
|N(u) \cup N(v)| = |N(u)| + |N(v)| - |N(u) \cap N(v)|.
$$
(v). $|N(u)| = d(u)$ and $|N(v)| = d(v)$ because $G$ is a simple graph.
(vi).
$$
|N(u) \cup N(v)| \leq n(G),
$$
as all vertices in the graph could potentially be in $N(u) \cup N(v)$.
(vii). Therefore:
$$
n(G) \geq d(u) + d(v) - |N(u) \cap N(v)|.
$$
(viii). As mentioned in (ii), the number of triangles containing $uv$ is the same as the size of $N(u) \cap N(v)$.
Thus, $uv$ belongs to at least:
$$
d(u) + d(v) - n(G)
$$
triangles.