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

In summary, we have proven that if G is a graph of order n such that D(G) + d(G) is greater than or equal to n-1, then G is connected and diam(G) is less than or equal to 4. We have also shown that the bound n-1 is sharp by providing a counterexample.
  • #1
King Tony
12
0

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].
 
Physics news on Phys.org
  • #2




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
 

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

1. What is Graph Theory?

Graph Theory is a branch of mathematics that studies the properties and relationships of graphs, which are mathematical structures used to model pairwise relationships between objects.

2. Why is Graph Theory important?

Graph Theory has numerous applications in various fields such as computer science, biology, social sciences, and transportation systems. It provides a framework for analyzing and solving problems involving networks and relationships between objects.

3. What is a proof in Graph Theory?

A proof in Graph Theory is a logical argument that demonstrates the validity of a statement or theorem about graphs. It involves using mathematical techniques and reasoning to show that a statement is true for all possible cases.

4. How do I approach a proof in Graph Theory?

The key to approaching a proof in Graph Theory is to understand the definitions, theorems, and techniques related to graphs. It is also important to carefully analyze the given problem and come up with a clear and organized approach to proving the statement.

5. Are there any tips for writing a clear and concise proof in Graph Theory?

Yes, some tips for writing a clear and concise proof in Graph Theory include clearly defining all terms and concepts, using logical and organized reasoning, and providing sufficient explanations and justifications for each step. It is also important to proofread and revise the proof for any errors or gaps in logic.

Back
Top