Definition:Connected (Graph Theory)/Graph

From ProofWiki
Jump to navigation Jump to search

Definition

Let $G$ be a graph.

Then $G$ is connected if and only if every pair of vertices in $G$ is connected.


Disconnected

Let $G = \struct {V, E}$ be a graph.

Then $G$ is disconnected if and only if it is not connected.

That is, if and only if there exists (at least) two vertices $u, v \in V$ such that $u$ and $v$ are not connected.


Examples

Arbitrary Example 1

The following is an example of a connected graph with $5$ vertices and $6$ edges.

Connected-graph.png

Vertex $C$ is adjacent to vertex $A$ but not to vertex $B$

There are $2$ paths of length $2$ from $B$ to $C$, that is $\tuple {B, A, C}$ and $\tuple {B, D, C}$

There are a several cycles, including $\tuple {B, D, E, B}$.


Also see


Sources