1
$\begingroup$

Consider a graph $G$ of $n$ vertices with minimum degree of a node $\delta (G)$ and maximum degree of a node $\Delta (G)$, prove that if $\delta(G) + \Delta (G) \ge n-1$, then $G$ is connected and diameter $\le 4$.

Definitions:

  • Diameter of a graph is the maximum distance between any two pair of vertices.
  • Distance of two vertices is the minimum path value between those two nodes.

My not-so-sure solution: Let $u$ and $v$ be the vertices with maximum and minimum degree repectively. If $u$ and $v$ are adjacent then according to conditions, there can be diameter of atmost 2. If the vertices are not adjacent then it can be proved that there must be a common vertex adjacent to both $u$ and $v$. If this is possible then we can have any path length of atmost value 4, which goes through this common vertex.

$\endgroup$
  • $\begingroup$ Isn't it interesting? Is it trivial? If yes, Why downvotes? $\endgroup$ – madhur4127 Sep 17 '18 at 6:15
  • $\begingroup$ Welcome to MSE. While I'm not one of the down voters, I'm sure that people are down voting, and voting to close, because you have simply given us a homework problem, without indicating that you have attempted to solve the problem yourself. What are your thoughts on the problem? What have you tried? How far did you get? Where are you stuck? Please respond in the body of the question; many people will vote to close without looking at the comments. $\endgroup$ – saulspatz Sep 17 '18 at 6:39
  • $\begingroup$ thanks @saulspatz, I added my solution, which I suppose is correct. I needed a good proof, by good I mean which is non-intuitive like those in classical graph theory. $\endgroup$ – madhur4127 Sep 17 '18 at 7:24
  • $\begingroup$ Maybe I'm just sleepy, but I don't follow your proof at all. It seems like a bunch of unproved assertions to me; I don't see why any of them are true. $\endgroup$ – saulspatz Sep 17 '18 at 7:31
1
$\begingroup$

Firstly you prove that $\delta$ and $\Delta$ have a common neighbor. Then you prove that the graph must be connected, otherwise in the other part of the graph, the vertices have smaller degree than $\delta$. To prove the diameter part, you use a degree of any vertex, which is bigger than $\delta$ thus has a common neighbor with $\Delta$, for the same reason $\delta$ had. And that will be the end of the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.