# Connectivity

(Redirected from Connected graph)
The ${\displaystyle \{6/2\}}$ hexagram is not connected but the ${\displaystyle \{8/3\}}$ octagram is.

Connectivity or connectedness is a property of polytope like object with several closely related formulations.

## Abstract Polytopes

Abstract polytopes are typically required to be strongly connected. This condition may be relaxed to allow for compounds, but it also allows for additional shapes that are not compounds, such as polyhedra with compound faces.

### Connectivity

A bounded poset is said to be connected if it is rank 1 or if for any two proper elements F  and G , there exists a sequence ${\displaystyle (F_{1},\ldots ,F_{n})}$ of proper elements such that ${\displaystyle F=F_{1}}$, ${\displaystyle G=F_{n}}$, and any ${\displaystyle F_{i},F_{i+1}}$ are comparable.[1] The special concession that rank 1 polytopes are connected ensures that the dyad is connected and thus an abstract polytope.

### Strong connectivity

Strong connectivity is a version of connectivity used in the definition of abstract polytope. A bounded poset is strongly connected iff every section is connected.

Note that this requires every section not just every proper section to be connected. In general every proper section of a poset being connected does not imply that the poset itself is connected.[1] Polytope compounds are exactly those posets such that every proper section is connected but the poset is not connected.

Strong connectivity is desired for abstract polytopes since we want sections of abstract polytopes to be themselves abstract polytopes. Strong connectivity ensures not only that the poset itself is not a compound but also that it doesn't have compound faces, edges etc.

#### Example

A dihedron with tetragramal faces ({4/2,2}) is connected but not strongly connected. If we draw its Hasse diagram we can see that the section highligted in red is a tetragram and thus is not connected.

This obeys the other requirements of an abstact polytope (it is dyadic, ranked and bounded) thus if the strongly connected requirement was weakened to only require posets to be connected this would be an abstract polytope.

### Flag connectivity

Two flags are said to be adjacent iff they differ by exactly one element. A ranked bounded poset is flag connected iff for any two flags ${\displaystyle \Phi }$ and ${\displaystyle \Psi }$, there exists a sequence of flags ${\displaystyle (\Phi _{1},\ldots ,\Phi _{n})}$ such that ${\displaystyle \Phi =\Phi _{1}}$, ${\displaystyle \Psi =\Phi _{n}}$, and any pair of flags ${\displaystyle \Phi _{i}}$ and ${\displaystyle \Phi _{i+1}}$ are adjacent.

Flag connectivity is a stronger condition than connectivity. However flag connectivity can only be applied to ranked posets whereas connectivity can be applied to any bounded poset. In practice however abstract polytopes are required to be ranked and even weaker notions generally maintain this requirement. Any ranked poset that is flag connected is also connected.

#### Strong flag connectivity

A ranked bounded poset is strongly flag connected iff every section is flag connected. On ranked bounded posets strong flag connectivity is equivalent to strong connectivity.[2]

## Graphs

A graph is connected if for any two vertices v  and v'  there is a sequence of vertices ${\displaystyle \{v\}_{1}^{n}}$ such that:

• ${\displaystyle v_{1}=v}$
• ${\displaystyle v_{n}=v'}$
• For every i , ${\displaystyle v_{i}}$ is adjacent to ${\displaystyle v_{i+1}}$. that is there is an edge between the two.

Intuitively this is the same as saying you can get from any one vertex to any other simply by following edges.

### Flag graphs

The flag graph of the ${\displaystyle \{6/2\}}$ hexagram is not connected.

The flag graph of a ranked poset is connected iff the poset is flag connected.

The graph based definitions of complex and maniplex, which generalize the idea of a flag graph, both require the graph to be connected.

## Sources

• McMullen, Peter; Schulte, Egon (December 2002), Abstract Regular Polytopes (1st ed.), Cambridge University Press, ISBN 0-521-81496-0