# Questions tagged [connected]

The tag has no usage guidance.

14 questions
Filter by
Sorted by
Tagged with
66 views

### Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)

Given undirected and connected graph $G = (V,E)$. Prove for any DFS run: for any $u,v \in V$ if $u.d>v.d$ then $u.d − v.d ≥ δ(u,v)$ $δ(u,v)$-distance of a shortest path (not necessarily unique) in ...
19 views

### Decremental connectivity on general graphs

I'm looking for an efficient solution to the problem of tracking the number of connected components in a general graph under edge deletions. General connectivity algorithms like that from Holm, ...
54 views

### Is every graph with minimum degree $n/2$ connected?

Claim: Let $G$ be a graph on $n$ nodes, where $n$ is an even number. If every node of $G$ has degree at least $n/2$, then $G$ is connected. Decide whether the above claim is true or false, and ...
548 views

### Tarjan's SCC : example showing necessity of lowlink definition and calculation rule?

Several questions (1, 2) have been asked about this topic already but I am trying to be more specific. In Tarjan's SCC algorithm, the calculation of lowlink when encountering a vertex which is ...
214 views