Doubt regarding strong component in a graph

Question

I know that strong component in a graph means between any 2 vertices there should be bi-directional path.

My doubt is cycle is always a strong component. can there be any other subgraph with some property P so that it is strong component ie., P implies strong component.

Answer 1

Your question is a bit too broad. There can be a lot of properties $P$ such that if $H$ is a subgraph of $G$ and $P(H)$ holds then all vertices of $H$ are in the same strong component.

For example:

• $P(H) = $ true iff H is a (directed) clique
• $P(H) = $ true iff H contains only one vertex
• $P(H) = $ true iff for every edge $(u,v)$ of $H$, $(v,u)$ is also in $H$.
• $P(H) = $ true iff $H$ has $n>1$ vertices and more than $(n-1)^2$ edges.
• ...

You can prove that the last condition implies that the vertices of $H$ are in a strong component by induction on $n$.

If $n=2$ then the graph has more than $1^2 = 1$ edge, i.e., it has at least two edges. The claim trivially follows.

If $n>2$, then let $H'$ be any (not necessarily proper) subgraph of $H$ with $(n-1)^2+1$ edges. Pick a vertex $v$ of minimum degree in $H'$. The degree $\delta$ of $v$ is at most $\frac{(n-1)^2+1}{n}$. Therefore $H-v$ has $n-1$ vertices and at least $(n-1)^2 + 1 - \delta = \frac{n(n-1)^2+n - (n-1)^2 - 1}{n} > (n-2)^2$ edges. By inductive hypothesis $H-v$ is strongly connected. The claim follows since $\delta$ is at least $(n-1)^2 + 1 - (n-1)(n-2) = (n-1)(n-1 -n +2) = (n-1) + 1 = n$, showing that $v$ has at least one incoming and one outgoing edge.

Answer 2

A strong component in a graph $G$, is a group of vertices $V_s$ such that $\forall v_1,v_2\in V_s:\exists u_1,...,u_n\in V_s:v_1=u_1\rightarrow u_2\rightarrow...\rightarrow u_n=v_2$.

In simpler terms: It means that every two nodes have a path between them (going through only vertices in the strong component).

In the case of a cycle: say, $v_1\rightarrow ...\rightarrow v_k\rightarrow v_1$ is the cycle, then it would be a strong component as every two vertices in it have a path between them.

There could be other cases with strong components, but every (non-trivial) strong component contains a cycle as we know $v\in V_s$ implies there is a path between $v$ and $v$ with nodes within $V_s$.

Furthermore, every (non-trivial) strong component $V_s=\{v_1,...,v_n\}$ has a cycle that goes through every node. Just take the path between $v_1$ and $v_2$, concatenate it with the path from $v_2$ to $v_3$ and so on (and finally also the path between $v_n$ and $v_1$).