0
$\begingroup$

Suppose G is a connected, undirected graph with at least 3 vertexes. we know the order or visiting the vertexes in DFS and BFS search is the same. Which of them is false?

1) G can be a completed graph.

2) diameter of G is at most 2.

3) G can be a bipartite graph.

4) G should be a tree or completed graph.

in one solution of exam, wrote (2) and (4) is solution of this question. anyone could describe me why? and why others is false?

$\endgroup$
0
$\begingroup$

We can use proof by construction here.

Assume, both DFS and BFS visit start from the same vertex, say $a$. Now we add two vertices such that the graph is connected and has same visiting order in DFS and BFS. This can be done in following two ways,

      a
     / \
    b   c

  figure: 1

or,

       a
      /
     b
    /
   c 

  figure: 2

The order of visit is $a,b,c$.
So, graph or tree having same order of visit in DFS and BFS for at least 3 vertices exists.

Now, let's add another vertex $d$. In the first figure we can add $d$ as a children of $b$. Then, in DFS vertex $d$ will be visited next to $b$, where in BFS it will be visited next to $c$. To solve this problem what we can do is to connect $a$ and $d$. Which will look like this:

       a
     / | \
    b  |  c
    \  |
      d

Now, the graph contains four vertices and has same order of visit in both DFS and BFS. If $b$,$c$ and $d$,$c$ is connected the graph becomes a complete graph and maintains the same order of visit. So, we can say, "$G$ can be a complete graph."

In another way in figure 2, $d$ can be added next to $c$ and this holds the same property:

      a
     / 
    b
   / 
  c
 /
d

But in this case the diameter has become 3. This concludes, "Diameter of $G$ can be greater than 2". We can easily show that this can also be a bipartite graph. So, we can say "$G$ can be a bipartite graph."

We have seen that graph $G$ can be a tree or a complete graph. But it is not "necessary" to be a tree or complete graph for having same visiting order in both DFS and BFS. So, "$G$ can be a 'tree' or 'complete graph' but it is not a necessary condition which was meant by the 'should be' statement".

$\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.