Graph DFS, BFS and some inference

Question

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?

Answer 1

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".