AGT Tut 2.1 solution

Theorem: Degree Sum Equality in Bipartite Graphs

For a bipartite graph $G=(V,E)$ with partite sets $X$ and $Y$ (where $V=X\cup Y$ and $X\cap Y=\varnothing$), the sum of the degrees of vertices in $X$ equals the sum of the degrees of vertices in $Y$:

${\sum }_{x\in X}deg(x)={\sum }_{y\in Y}deg(y)$

Proof by Induction

We will use induction on the number of edges, $m=|E|$.

Base Case: ($m=0$)

If $|E|=0$, the graph has no edges. Thus, all vertices have a degree of $0$. Therefore:

${\sum }_{x\in X}deg(x)=0={\sum }_{y\in Y}deg(y)$

The base case holds.

Inductive Hypothesis:

Assume the theorem holds for any bipartite graph with $k$ edges, where $k\ge 0$. That is, for a bipartite graph $G=(V,E)$ with partite sets $X$ and $Y$, and $|E|=k$:

${\sum }_{x\in X}deg(x)={\sum }_{y\in Y}deg(y)$

Inductive Step:

We need to show that the theorem holds for a bipartite graph with $k+1$ edges.

Consider a bipartite graph $G^{\prime }=(V^{\prime },E^{\prime })$ with partite sets $X^{\prime }$ and $Y^{\prime }$, and $|E^{\prime }|=k+1$.

Remove an arbitrary edge $e=\{u,v\}$ from $G^{\prime }$. Since $G^{\prime }$ is bipartite, one vertex of $e$ must be in $X^{\prime }$ and the other in $Y^{\prime }$. Without loss of generality, let $u\in X^{\prime }$ and $v\in Y^{\prime }$.

This removal results in a new graph $G=(V,E)$ where $V=V^{\prime }$, $X=X^{\prime }$, $Y=Y^{\prime }$, and $E=E^{\prime }\setminus \{e\}$, with $|E|=k$.

By the inductive hypothesis, for graph $G$:

${\sum }_{x\in X}de{g}_G(x)={\sum }_{y\in Y}de{g}_G(y)$

Now, add the edge $e=\{u,v\}$ back to $G$ to obtain the original graph $G^{\prime }$. This increases the degree of $u$ (in $X^{\prime }=X$) by 1 and the degree of $v$ (in $Y^{\prime }=Y$) by 1.

Therefore:

${\sum }_{x\in X^{\prime }}de{g}_{G^{\prime }}(x)={\sum }_{x\in X}de{g}_G(x)+1$

and

${\sum }_{y\in Y^{\prime }}de{g}_{G^{\prime }}(y)={\sum }_{y\in Y}de{g}_G(y)+1$

Combining these with the inductive hypothesis:

${\sum }_{x\in X^{\prime }}de{g}_{G^{\prime }}(x)={\sum }_{y\in Y^{\prime }}de{g}_{G^{\prime }}(y)$

Thus, the theorem holds for a bipartite graph with $k+1$ edges.

Conclusion:

By the principle of mathematical induction, the theorem holds for all finite bipartite graphs:

${\sum }_{x\in X}deg(x)={\sum }_{y\in Y}deg(y)$