What is tangled graph

929 Views Asked by At

Text I was reading states:

An $n$-node graph $G=(V,E)$ is said to be tangled if there is an edge leaving every set of $\lceil\frac n3 \rceil$ or fewer vertices. As a special case, the graph consisting of a single node is considered tangled.

Does this mean if we take any subset $S$ of vertices $V$ such that |S|$\le\lceil\frac n3 \rceil$, then there is an edge connecting a vertex $v \in S$ with a vertex $u \in V-S$?

It will also be helpful if someone can give an example.

1

There are 1 best solutions below

0
On

Yep, that's the idea. Equivalently, every component of $G$ has size strictly bigger than $\lceil \frac n3 \rceil$.

So all connected graphs are examples of tangled graphs. Also, we can prove that a tangled graph has at most two components (if there were three components, then one of them would have to contain at most $\frac n3$ vertices).