retagged by
1,029 views
1 votes
1 votes

In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote bt $P$ the following property: there exists a vertex that is a neighbour of all other vertices. Consider the following statements:

  1. If $P$ is false, then there is a pair of vertices such that the distance between them is at least $4.$
  2. If $P$ is true, then the distance between any pair of vertices is at most $2.$

What can you say about these statements?

  1. Only i is true
  2. Only ii is true
  3. Both i and ii are true
  4. Neither i nor ii is true
retagged by

2 Answers

0 votes
0 votes

B.

1. This can be negated by taking an example. Eg: In CP is violated, but max distance between any pair = 2. 

2. This is true. Let u and v be 2 vertices such no edge (u,v). Let r be central vertex. Then u can reach v through r. Thus, max distance between any 2 vertices = d(u,r)+d(r,v) = 1+1=2.

Answer:

Related questions

1 votes
1 votes
2 answers
2
1 votes
1 votes
2 answers
3
go_editor asked Dec 30, 2016
549 views
A dodecahedron is a regular solid with $12$ faces, each face being a regular pentagon. How many edges are there? And how many vertices?$60$ edges and $20$ vertices$30$ ed...
1 votes
1 votes
2 answers
4
go_editor asked Dec 30, 2016
759 views
An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example:Show that for every undirected graph, there is a way...