# Doubt regarding strong component in a graph

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.

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.

• Sir i recently started studying graphs from corman. I was just thinking what all other properties could make it strong component. can you please elaborate, if possible, on your last 2 points (atleast some google links is also fine. Searched but could not find) – Nascimento de Cos Jun 9 '20 at 12:54

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$$).

• You are right. I will fix it to every non-trivial strong component (aka, every strong component with at least 2 nodes) – nir shahar Jun 9 '20 at 13:15