Let $$G$$ be a simple undirected graph. Let $${T_D}$$ be a depth first search tree of $$G.$$ Let $${T_B}$$ be a breadth first search tree of $$G.$$ Consider the following statements.

$$(I)$$ No edge of $$G$$ is a cross edge with respect to $${T_D}.$$ ($$A$$ cross edge in $$G$$ is between
$$\,\,\,\,\,\,\,\,$$ two nodes neither of which is an ancestor of the other in $${T_D}.$$)
$$(II)$$ For every edge $$(u,v)$$ of $$G,$$ if $$u$$ is at depth $$i$$ and $$v$$ is at depth $$j$$ in $${T_B}$$, then
$$\,\,\,\,\,\,\,\,\,\,\,$$ $$\left| {i - j} \right| = 1.$$

Which of the statements above must necessarily be true?

Let $$G$$ be a graph with $$100!$$ vertices, with each vertex labelled by a distinct permutation of the numbers $$1,2, … , 100.$$ There is an edge between vertices $$u$$ and $$v$$ if and only if the label of $$u$$ can be obtained by swapping two adjacent numbers in the label of $$v.$$ Let $$𝑦$$ denote the degree of a vertex in $$G,$$ and $$𝑧$$ denote the number of connected components in $$G.$$ Then, $$𝑦 + 10𝑧 =$$ _____.

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let $$n$$ denote the number of nodes in the queue. Let $$enqueue$$ be implemented by inserting a new node at the head, and $$dequeue$$ be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of $$enqueue$$ and $$dequeue,$$ respectively, for this data structure?

In an Entity-Relationship $$(ER)$$ model, suppose $$R$$ is a many-to-one relationship from entity set $$E1$$ to entity set $$E2.$$ Assume that $$E1$$ and $$E2$$ participate totally in $$R$$ and that the cardinality of $$E1$$ is greater than the cardinality of $$E2$$

Which one of the following is true about $$R$$?