Thread: Graphs, Diameter related question.

I have been trying to solve this question for a while now and the deadline is almost over so I have no option but to seek help.

We have an undirected graph of edges and we know that the degree of each edge is the object is to prove that the diameter is . How can I do that?

EDIT:
we have vertexes and the degree of each vertex is

[Edit: Do you really mean degree of each edge? or vertex? I am proceeding on the assumption that its the degree of a vertex]

The diameter is the longest distance from any vertex to another vertex.

Start at any vertex. The maximum number of other vertices reachable in one step is .
Maximum reachable in 2 steps is .
Argue that you cannot reach all vertices in 3 steps (so diameter greater than 3.

Originally Posted by snowtea

The diameter is the longest distance from any vertex to another vertex.

Start at any vertex. The maximum number of other vertices reachable in one step is .
Maximum reachable in 2 steps is .
Argue that you cannot reach all vertices in 3 steps (so diameter greater than 3.

Thank you for your reply, I am not sure I understand the process
lets say I take a graph of with if I choose one of the vertexes and go from there I would be able to reach other vertex therefore in one step I have covered of the vertexes in the graph then in the second step from each of the new vertexes I've reached I would try to get their degree to but each of them already has so I will be drawing from each, in reality I would have already covered out of the vertexes while in calculations I would have or if I keep the actual values what am I missing?

EDIT:
Sorry I have misunderstood the suggested solution though I still am unable to comprehend it properly.
Starting at any vertex the maximum number of other vertices reachable in one step is and not .
Maximum reachable in 2 steps is in my previous example over vertexes we would have vertices when we would actually have on graph

Alright, think of it like this.

Start at a vertex v. Using the technique above, show that there is at least one vertex w which cannot be reached by v in 2 steps (just one is enough).

So we know that there exists v and w such that their distance is at least 3. This means all the neighbors of v and w are different.

Now draw all the neighbors of v and all the neighbors of w. Argue by the maximum degree, either v and w have distance > 3, or some pair of neighbors have distance > 3.

Originally Posted by snowtea

Alright, think of it like this.

Start at a vertex v. Using the technique above, show that there is at least one vertex w which cannot be reached by v in 2 steps (just one is enough).

So we know that there exists v and w such that their distance is at least 3. This means all the neighbors of v and w are different.

Now draw all the neighbors of v and all the neighbors of w. Argue by the maximum degree, either v and w have distance > 3, or some pair of neighbors have distance > 3.

Thanks again for your help
I think I understand the solution this time
basically starting from vertex x and drawing vertices then starting from the new vertexes we arrived to we draw vertices from each so we got so far up to (the starting vertex) which is equal to however we know that the degree is actually in each vertex so we would have covered vertexes in 2 steps which will cause us to go at least one more step to cover all of the remaining vertexes making the diameter length which is equal to .

That is what I understood so far as for the last line for drawing all of the neighbors of v and all of the neighbors of w well I did try drawing them over and the diameter was actually and not more, isn't the explenation above a full solution?

Yes, you are correct.

I misread the problem as diameter strictly greater than 3. However, with greater than or equal to 3, you have the full proof.

Originally Posted by snowtea

Yes, you are correct.

I misread the problem as diameter strictly greater than 3. However, with greater than or equal to 3, you have the full proof.

great! thank you very much for your time and effort, much appreciated