Graph Theory Proof Problem(Bipartites graphs)

Question

I'm struggling to proof something the Professor gave us. I asked several friends and no one knows what to do. Basically is this:

Prove for every simple bipartite Graph with $n \ge 1$ vertex: $$\delta(G)+\Delta(G)\le n.$$

Professor's Tip: Split you answer in two. First prove the follow:

If $G$ is simple and bipartite with at least $3$ vertices, $G$ has a vertex $v \in V(G)$ that satisfies at least one of these properties:

• $\Delta(G−v)=\Delta(G)$

• $\delta(G−v)= \delta(G)$

Now, prove by induction on $n$ using these properties.

Guys, I don't know where to start and how to use these information! I checked several books ([West], [Chartrand-Zhang] and [Diestel]) and none of them proved to be useful.

Sorry if my English was bad. Thanks!

Answer 1

You want to use that result in your induction step. Set up your base case (true for say, $n\le 3$) and let $G$ be a bipartite graph with $n > 3$ vertices. By the result in the tip given to you, there exists a vertex $v$ such that $\delta(G-v) = \delta(G)$ or $\Delta(G-v) = \Delta(G)$. Remove $v$ to obtain $G-v$. By the induction hypothesis we have $$\delta(G-v) + \Delta(G-v) \le n-1.$$ If $\delta(G-v) = \delta(G)$ and $\Delta(G-v) \ne \Delta(G)$ then we have $$\delta(G) + (\Delta(G)-1) \le n-1 \implies \delta(G) + \Delta(G) \le n$$ and similarly if $\Delta(G-v) = \Delta(G)$ and $\delta(G-v) \ne \delta(G)$. If both conditions are satisfied then we have $$\delta(G') + \Delta(G') \le n-1 \implies \delta(G) + \Delta(G) \le n-1\le n.$$

Answer 2

I don't know how to prove the tip, but the theorem is trivial. Suppose the parts are $V_1$ and $V_2$, that $|V_1|=n_1$ and $|V_2|=n_2$, where $n_1+n_2=n$. We may assume that $n_1\geq n_2$.

Every vertex in $V_1$ has degree at most $n_2$, and every vertex in $V_2$ has degree at most $n_1.$ Thus $\Delta(G)\leq n_1$, $\delta(G)\leq n_2,$ and the theorem follows.