Definition:Connected (Graph Theory)/Graph

From ProofWiki
Jump to navigation Jump to search


Let $G$ be a graph.

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


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.


Arbitrary Example 1

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


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