Ynoindent Ex$.5($True$/$false$)$

In this exercise, assume a graph $G=(V,E)$ where $V$ denotes the set of vertices, $E$ the set of ediges. As usual, $|V|-n,|E|=m.$

Justify: True or False: If $G$ is a cousected undirected graph then it is guarantered to have ot least $n-1$ edges

Justify: True or False: If $G$ is a strongiy connected uirected graph then it is guaranteed to have at least $n-1$ edges, $($Recall a "strongly connected" directed graph, is a directed groph in which for every pair of vertices $(a,b)$ there is a directed path from $a$ to $b$ and also there is a direcied a path from $b$ to $a.)$

Iustify: True or False: in a birected Acyelic Groph $($DAG$),$ the number of distinct paths between two vertices is at masi $|V{|}^2.$

justify: True or False: Every DAG has at least one sauree,

Fustify: True or False: Depth$-$litst search on a connected undirected graph $G$ will visit all of the vertices or $G.$

Justily: True or Fabe: Suppose we have a graph where each edge weight value appears at most twice. Then, there are at mast two minimum spanning trees in this graph.

Justify: True or False: Suppose we run DFS on an undigected graph and find exactly $17$ back edges.

Then the graph is guoranteed to have at least onc cycle.

Justily: True or False: DFS on a directed graph with $n$ vertices and at leust $n$ edges is guaranterd to

lind at least ne back edge.

Justify: True or False: DFS on an undirecled graph with $n$ vertices and at least $n$ edges is guarinteed

to find at Jeast ane back edge.

Justify: True or False: If wertices $u,v$ are not in the same strongly connected component of a directed graph

$G,$ then it is necessarily the case that $v$ is not reachable from $u$ in $G.($recall a "strongly" connected component of a directed graph is a connected component in which for every pair of vertices $(a,b)$ there is a path from $a$ to $b$ and also there is a path from $b$ to a$.)$