Proof that for all simple bipartite graph G with n>=1 vertices, minDeg(G) + maxDeg(G) is less or equal than n

Question

So I have this exercise I must do that asks me to:

Prove that for all simple bipartite graph G with n>=1 vertices, (minDeg(G) + maxDeg(G)) is less or equal than n.

As a tip, the exercise tells to divide the proof in two parts. First, prove the following lemma:

If G is a simple bipartite graph with at least 3 vertices, then G has SOME vertex that make AT LEAST ONE of the following statements true:

maxDeg(G-v) = maxDeg(G)

minDeg(G-v) = minDeg(G)

Then, prove the exercises's statement using the lemma and induction in n.

We are a group of 3 and no one found a way to even start this. Any insight will be appreciated.

Answer 1

Let us first prove the lemma. Let $G$ be a bipartite graph with at least $3$ vertices.

Let $w$ be a vertex in $G$ such that $\text{deg}(w) = \text{maxDeg}(G)$. We break into two cases.

Case 1: There exists a vertex $v$ such that $w$ and $v$ do not share an edge.

Consider $G-v$. Since $G$ is bipartite and has at least $3$ vertices, we have that $G-v$ is a bipartite graph. Also, we have that $\text{maxDeg}(G-v)=\text{maxDeg}(G)$ since all of the neighbors of $w$ are still in $G-v$.

Case 2: $w$ shares an edge with every other vertex

This implies that the bipartition consists of the vertex $w$ on one side and all other vertices on the other side (i.e. the two parts of our graph are the vertex $w$ and all other vertices). We have that the degree of all other vertices besides $w$ is equal to one. Note that since there are at least $3$ vertices, at least $2$ vertices must have degree $1$. Take $v$ to be one of the vertices of degree $1$. We have $G-v$ is bipartite and $\text{minDeg}(G-v)=\text{minDeg}(G)$.

This proves the lemma. Now we prove the exercise. We proceed by induction on the number of vertices.

Base Case: n=2

I'll leave this to you.

Inductive Step: Assume that for all bipartite graphs $G$ of degree $n$, we have $\text{minDeg}(G)+ \text{maxDeg}(G) \leq n$.

Let $H$ be an arbitrary bipartite graph with $n+1$ vertices. Since we assume $n\geq 2$, we have that $H$ has at least $3$ vertices. By our lemma, there exists a vertex $v$ such that $\text{maxDeg}(H-v)=\text{maxDeg}(H)$ or $\text{minDeg}(H-v)=\text{minDeg}(H)$.

Looking at $H-v$, we see that it is a bipartite graph with $n$ vertices. Thus by our inductive hypothesis, $\text{minDeg}(H-v)+\text{maxDeg}(H-v) \leq n$.

By adding a single vertex, the max degree and min degree can at most increase by one. However by our specific choice of $v$, we know that at most one of them will increase by one when we add back in $v$. This gives us $$\text{minDeg}(H)+\text{maxDeg}(H) \leq \text{minDeg}(H-v)+\text{maxDeg}(H-v)+1 \leq n+1$$

By induction, we have proven the statement.

Answer 2

That's far more complicated than it needs to be.

By definition, since $G$ is a bipartite graph its vertices can be partitioned into disjoint sets $T$ and $U$ such that all the edges are in $T \times U$. Without loss of generality let $|T| \le |U|$.

If $|T| = 0$, $\textrm{minDeg}(G) = \textrm{maxDeg}(G) = 0$ so the inequality holds.

Otherwise every vertex in (non-empty) $|U|$ has degree no greater than $|T|$, so $\textrm{minDeg}(G) \le |T|$. Similarly every vertex has degree no greater than $|U|$, so $\textrm{maxDeg}(G) \le |U|$. But the sum of upper bounds is an upper bound on the sum, so $\textrm{minDeg}(G) + \textrm{maxDeg}(G) \le |T| + |U| = n$.