Connected graph

Connected graph --- связный граф.

A graph [math]\displaystyle{ G }[/math] is a connected graph if for all [math]\displaystyle{ u,v \in V(G) }[/math], [math]\displaystyle{ u \neq v }[/math], there is a chain [math]\displaystyle{ (v_{1}, \ldots, v_{k}) }[/math] in [math]\displaystyle{ G }[/math] with [math]\displaystyle{ \{v_{1}, v_{k}\} = \{u,v\} }[/math], (the chain connects [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math]). Otherwise, the graph is called disconnected.

A graph [math]\displaystyle{ G = (V,E) }[/math] is maximum edge-connected (in short, max-[math]\displaystyle{ \lambda }[/math]) if [math]\displaystyle{ \lambda = [2q/p] }[/math], where [math]\displaystyle{ p = |V|, \; q = |E| }[/math] and [math]\displaystyle{ \lambda = \lambda(G) }[/math] is edge-connectivity of [math]\displaystyle{ G }[/math]. Note that the set of edges adjacent to a point [math]\displaystyle{ u }[/math] of degree [math]\displaystyle{ \lambda }[/math] is certainly a minimum edge-disconneting set. Similarly, [math]\displaystyle{ G }[/math] is maximum point-connected (in short, max-[math]\displaystyle{ \kappa }[/math]) if [math]\displaystyle{ \kappa = [2q/p] }[/math], where [math]\displaystyle{ \kappa = \kappa(G) }[/math] is the point-connectivity of [math]\displaystyle{ G }[/math]. Also, the set of points adjacent to [math]\displaystyle{ u }[/math] of degree [math]\displaystyle{ \kappa }[/math] is certainly a minimum point-disconnecting set. In this context, such an edge or a point set is called trivial. A graph [math]\displaystyle{ G }[/math] is called super edge-connected if [math]\displaystyle{ G }[/math] is max-[math]\displaystyle{ \lambda }[/math] and every minimum edge-disconnecting set is trivial. Analogously, [math]\displaystyle{ G }[/math] is super point connected if [math]\displaystyle{ G }[/math] is max-[math]\displaystyle{ \kappa }[/math] and every minimum point-disconnecting set is trivial.