Graph Theory Proof Help: Connectedness and Diameter Bound in Graphs of Order n

[King Tony]

Homework Statement

Prove that if G is a graph of order n such that D(G) + d(G) greater than or equal to n - 1, then G is connected and diam(G) less than or equal to 4. Show that the bound n -1 is sharp.

Note: D(G) is the max degree of any vertex in G and d(G) is the min degree of any vertex in G. My LaTeX code was very messed up so I was forced to remove all [ t e x ] and [ / t e x ] objects from the post as i was unable to fix them.

Homework Equations

handshaking lemma

The Attempt at a Solution

I don't really know what to start out with. Clearly the initial statement is implying something that I'm missing. My thinking is that the initial statement implies something along the lines of the max degree vertex and the min degree vertex being connected but I'm not exactly sure how to mathematically articulate it.

Thanks doods!

P.S. I'm very sorry that this is not in LaTeX. I'm not sure what was happening but my code was getting extremely messed up by just doing [tex] and [/tex].

 

[mighty2000]

Thank you for your post. Let me try to help you with your problem. First, let's define some terms to make sure we are on the same page.

A graph G is connected if there is a path between every pair of vertices in G. The diameter of a graph is the maximum distance between any two vertices in the graph. The handshaking lemma states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges in the graph.

Now, let's prove the given statement.
Suppose G is a graph of order n such that D(G) + d(G) greater than or equal to n - 1. This means that the sum of the max degree and min degree of any vertex in G is at least n-1.

First, let's prove that G is connected. Suppose G is not connected. This means there exists at least two vertices that are not connected by a path. Let's call these vertices u and v. Since G is not connected, there must be at least one vertex w that is connected to neither u nor v. This means that the degree of w is 0, which contradicts the given condition that d(G) is at least n-1. Therefore, G must be connected.

Next, let's prove that diam(G) is less than or equal to 4. Suppose diam(G) is greater than 4. This means that there exists two vertices u and v that are at least 5 edges apart. Since u and v are at least 5 edges apart, the degree of u and v must be at least 5 by the handshaking lemma. But this contradicts the given condition that D(G) is at most n-1. Therefore, diam(G) must be less than or equal to 4.

Lastly, let's show that the bound n-1 is sharp. Consider a complete graph of order n. In this graph, every vertex has a degree of n-1, and the max degree and min degree are both equal to n-1. This satisfies the given condition that D(G) + d(G) is at least n-1. However, the diameter of this graph is n-1, which is greater than 4. Therefore, the bound n-1 is sharp.

I hope this helps you understand the problem better. Let me know if you have any further questions