if G be a connected, undirected graph and has at least 3 vertex. we know the order of visiting node from a given vertex in BFS and DFS is the same. which of the following is false?
a) G can be a complete graph.
b) diameter of G is at most 2.
c) G can be a complete bipartite graph.
d) G must be a Tree or Complete Graph.
Anyone could help me for any hint or tutorial...
I actually think there are 2 false statements in there. I hope the following hints will help you.
EDIT : since OP has figured it out, I'll post the answers.
a) If $G$ is a complete graph, can you find an ordering of the vertices of $G$ that can not correspond to a DFS visiting order ? Can you find one that can't be done by a BFS ?
EDIT : a) is TRUE. Any vertex ordering can correspond to a visiting order of a BFS, or a DFS. So having the same order is possible.
b) Say $G$ is a path of length 4 (so the diameter is greater than 2), and say this path is $a \rightarrow b\rightarrow c\rightarrow d$. Do a BFS starting from $a$. Do a DFS starting from $a$.
EDIT : b) is FALSE. Both traversals will give the ordering $a,b,c,d$ when starting from $a$.
c) Look at a complete bipartite graph having one side with just a single vertex (a star tree). What if this vertex is the first visited by BFS or DFS.
EDIT : c) is TRUE. Both traversals can yield the same ordering when starting from the single vertex. Though I believe star trees are the only bipartite complete graphs with this property.
d) Take a complete graph having at least 4 vertices, and remove a single edge $e$. It's not a tree, nor a complete graph. Start visiting from a vertex $v$ not incident to $e$.
EDIT : d) is FALSE. Starting from $v$, all orderings of the other vertices are possible in both traversals.