Let u and v be adjacent vertices in a simple graph G. Prove that uvbelongs to at least $$ d(u) + d(v) - n(G) $$ triangles in G.

문제출처 - 광주과학기술원(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.