How to find if a graph is a tree and its center

Question

Is there an algorithm (or a sequence of algorithms) to find, given a generic graph structure G=(V,E) with no notion of parent node, leaf node and child node but only neighboordhood relations:

1) If G it is a tree or not (is it sufficient to check |V| = |E|+1?)

2) If the graph is actually a tree, the leaves and the center of it? (i.e the node of the graph which minimizes the tree depth)

Thanks

Answer 1

If the "center" of the tree is defined as "the node of the graph which minimizes the tree depth", there's an easier way to find it than finding the diameter.

d[] = degrees of all nodes
que = { leaves, i.e  i that d[i]==1}
while len(que) > 1:
  i=que.pop_front
  d[i]--
  for j in neighbors[i]:
    if d[j] > 0:
      d[j]--
      if d[j] == 1 :
        que.push_back(j)

and the last one left in que is the center.

you can prove this by thinking about the diameter path. to simpify , we assume the length of the diameter path is odd, so that the middle node of the path is unique, let's call that node M,

we can see that:

1. M will not be pushed to the back of que until every node else on diameter path has been pushed into que
2. if there's another node N that is pushed after M has already been pushed into que, then N must be on a longer path than the diameter path. Therefore N can't exist. M must be the last node pushed (and left) in que

Answer 2

For (1), all you have to do is verify |V| = |E| + 1 and that the graph is fully connected.

For (2), you need to find a maximal diameter then pick a node in the middle of the diameter path. I vaguely remember that there's an easy way to do this for trees.

You start with an arbitrary node a, then find a node at maximal distance from a, call it b. Then you search from b and find a node at maximal distance from b, call it c. The path from b to c is a maximal diameter.

There are other ways to do it that might be more convenient for you, like this one. Check Google too.

Answer 3

1. No, it is not enough - a tree is a CONNECTED graph with n-1 edges. There could be n-1 edges in a not connected graph - and it won't be a tree.
   You can run a BFS to find if the graph is connected and then count the number of edges, that will give you enough information if the graph is a tree

2. The leaves are the nodes v with degree of the nodes denoted by d(v) given by the equation d(v) = 1 (which have only one connected vertex to each)

---

(1) The answer assumes non-directed graphs
(2) In here, n denotes the number of vertices.