Definition:Connected (Graph Theory)/Graph

From ProofWiki
Jump to navigation Jump to search

Definition

Let $G$ be a graph.

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


Disconnected

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

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

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


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

  • Results about connected graphs can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Connected_(Graph_Theory)/Graph&oldid=737044"