Why are back edges and forward edges said to be impossible in BFS for an undirected graph?

Question

Is it true that there are no back edges and no forward edges in a BFS of an undirected graph?
I feel this is incorrect. Here is my counterexample (graph is represent using adjacency list):

    0 : 1
    1 : 0, 1, 2
    2 : 1, 3, 3
    3 : 2, 2

In this example, the vertices are numbered from 0 to 3, and we have a self-loop and multiple edges between vertices 2 and 3. After preforming a BFS on this graph, we get a tree (0-1-2-3), where the vertices to the right of a vertex are its descendants. The self-loop is on vertex 1. Based on the definitions, it could be either a forward or a back edge. We also have a multiple edges from 2 to 3. One these edge will be tree edge, but the other will either be a forward or a back edge.

What I’m concerned about is that the internet says no back edges and no forward edges are possible, and even the CLRS textbook states this. Here's the text from the book:

[...]Prove that in a breadth-first search of an undirected graph, the following properties hold:

1. There are no back edges and no forward edges.
2. For each tree edge (u, v), we have v.d = u.d + 1.
3. For each cross edge (u, v), we have v.d = u.d or v.d = u.d + 1.

Am I missing something here?

Answer 1

When it comes to the concept of an undirected graph, definitions vary.

Wikipedia - Undirected graph informs (I added the exclamation mark):

... 𝐸 is a set(!) of unordered pairs {𝑣₁, 𝑣₂} of vertices ...

A multigraph is a generalization that allows multiple edges to have the same pair of endpoints. In some texts, multigraphs are simply called graphs.

Sometimes, graphs are allowed to contain loops, which are edges that join a vertex to itself. To allow loops, the pairs of vertices in 𝐸 must be allowed to have the same node twice.

So, it is important to identify the definition that an author uses when analysing a claim they make that concerns undirected graphs.

In the case of the internet article you linked to, I did not find their definition of undirected graph.

However, CLRS does not allow self-loops or multiple edges between the same vertices in its definition of undirected graphs. It distinguishes this type of graph from a "multi-graph" in annex B.4:

In an undirected graph, self-loops are forbidden

[...]

A multi-graph is like an undirected graph, but it can have both multiple edges between vertices and self-loops

So this explains why CLRS concludes "there are no back edges and no forward edges" in a BFS traversal.