Graph Theory Proof(Help!!!)

[Lairon]

Hi everyone

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

"Proof for every simple bipartite Graph with n ≥ 1 vertex:

δ(G)+∆(G)≤ n.

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

If G is simple and bipartite with at least 3 vertex, so G has a vertex v ∈ V(G) that satysfies at least one of these properties:

• ∆(G−v)=∆(G)
• δ(G−v)= δ(G)

Now, proove by induction of 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 no one of them proved to be useful.

Sorry if my english was bad. Thanks!

 

[pka]

"Proof for every simple bipartite Graph with n ≥ 1 vertex:
δ(G)+∆(G)≤ n.
Professor's Tip: Split you answer in two. First prove the follow:
If G is simple and bipartite with at least 3 vertex, so G has a vertex v ∈ V(G) that satysfies at least one of these properties:
• ∆(G−v)=∆(G)
• δ(G−v)= δ(G)
Now, proove by induction of 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 no one of them proved to be useful.

Here is the trouble with your post, Because Graph Theory is such a new field there is no standard notation. Ever though I have taught it and have several textbooks with material on graph theory, I have no idea what those symbols mean. I am fully aware what a bipartite graph is and have seen \(\displaystyle V(G)\) used as the vertex set of the graph \(\displaystyle G\) I have no idea what \(\displaystyle \Delta(G-v), ~\delta(G-v),~\Delta(G),~\delta(G)\) means.
So if we are to help then you must define all terms completely .

 

[Lairon]

Here is the trouble with your post, Because Graph Theory is such a new field there is no standard notation. Ever though I have taught it and have several textbooks with material on graph theory, I have no idea what those symbols mean. I am fully aware what a bipartite graph is and have seen \(\displaystyle V(G)\) used as the vertex set of the graph \(\displaystyle G\) I have no idea what \(\displaystyle \Delta(G-v), ~\delta(G-v),~\Delta(G),~\delta(G)\) means.
So if we are to help then you must define all terms completely .

~\delta(G)$ = the minimum degree in the graph
~\Delta(G) = the maximum degree in the graph

(G-v) in both mean to take one vertex of the graph. Basically, taking one v maintains at least one of the maximum or minimum degrees.

 

[pka]

~\delta(G)$ = the minimum degree in the graph
~\Delta(G) = the maximum degree in the graph
(G-v) in both mean to take one vertex of the graph. Basically, taking one v maintains at least one of the maximum or minimum degrees.

Thank you for the clarification. I see the logic of the question now.
But one more, does "n ≥ 1 vertex: " mean that there are \(\displaystyle \bf n\) vertices or does it mean some vertex has degree \(\displaystyle \ge 1~?\)

 

[Lairon]

Thank you for the clarification. I see the logic of the question now.
But one more, does "n ≥ 1 vertex: " mean that there are \(\displaystyle \bf n\) vertices or does it mean some vertex has degree \(\displaystyle \ge 1~?\)

Yeah, Vértices. English is not my first language, and I still mixes vertex with vertices

 

[pka]

Yeah, Vértices. English is not my first language, and I still mixes vertex with vertices

So,we have a bipartite graph, \(\displaystyle G\) with non-degenerate vertices for which you are to prove that the maximum degree plus the minimum degree is no more than \(\displaystyle n\) i.e. \(\displaystyle \Delta(G)+\delta(G)\le n\) Is that as you understand the question?

 

[Lairon]

So,we have a bipartite graph, \(\displaystyle G\) with non-degenerate vertices for which you are to prove that the maximum degree plus the minimum degree is no more than \(\displaystyle n\) i.e. \(\displaystyle \Delta(G)+\delta(G)\le n\) Is that as you understand the question?

Precisely! And If I use this:

• ∆(G−v)=∆(G)
• δ(G−v)= δ(G)

I will need to proof it as well