Recent questions tagged graph-connectivity

Suppose we run DFS on an undirected graph, and we discover a vertex $v$ with:$\mathrm{pre}(v)=1$ and $\mathrm{post}(v)=2|V|$Then the graph must be connected.True False

For a graph $G=(V, E)$ and a subset $X \subseteq V$ of the vertices, the induced subgraph $G[X]$ is defined as $G[X]=\left(X, E^{\prime}\right)$, where $E^{\prime}=\{u v ...

 How many of the following given set of vertices is/are CORRECT strongly connected components for the given directed graph?$C$$A$$E$$IC$$F$$IDE$$I$$H$$GJ$

​​​​Let $\text{A}$ be the adjacency matrix of a simple undirected graph $\text{G}$. Suppose $\text{A}$ is its own inverse. Which one of the following statements is always...

Let $\text{G}$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $\text{G}$ has even weight. Which o...

The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________.

A strongly connected component $(\mathrm{SCC})$ of a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ is a maximal set of vertices such that any two vertices in the s...