EF Connected vertices, graphs, and components

🔗

Section 15.3 Connected vertices, graphs, and components

🔗

connected vertices: 🔗
a pair of vertices $v, v^{'}$ such that there exists a walk beginning at $v$ and ending at $v^{'}$
connected graph: 🔗
every pair of vertices is connected

🔗

Example 15.3.1. A connected graph.

A diagram of an example connected graph.

🔗

Example 15.3.2. A nonconnected graph.

A diagram of an example nonconnected graph.

🔗

Being connected is a symmetric relationship between vertices, and walks connecting vertices can be shortened to paths.

🔗

Proposition 15.3.3. Characterizations of connected vertices.

🔗

Assume

v, v^{'}

are vertices in a graph. Then the following are equivalent.

🔗
Vertices $v, v^{'}$ are connected.
🔗
There exists a walk beginning at $v$ and ending at $v^{'} .$
🔗
There exists a path beginning at $v$ and ending at $v^{'} .$
🔗
There exists a walk beginning at $v^{'}$ and ending at $v .$
🔗
There exists a path beginning at $v^{'}$ and ending at $v .$

🔗

Proof idea.

As usual, we prove the equivalence of multiple statements using a cycle of logical implications.

Statement 1 implies Statement 2.

This is the definition of connected vertices.

Statement 2 implies Statement 3.

Suppose

v_{0}, e_{1}, v_{1}, \dots, v_{n - 1}, e_{n}, v_{n}

is a walk with

v_{0} = v

and

v_{n} = v^{'} .

If this walk is not a path, then there is a repeated vertex. Suppose

v_{j} = v_{i}

with

j > i .

Then

v_{0}, e_{1}, v_{1}, \dots, v_{i - 1}, e_{i}, v_{j}, e_{j + 1}, \dots, v_{n - 1}, e_{n}, v_{n}

is also a walk from

v

v^{'} .

Keep removing repeated vertices in this way until a path is obtained.

Statement 3 implies Statement 4.

Just reverse the order of the vertices and edges in the path from

v

v^{'}

to obtain a walk in the other direction.

Statement 4 implies Statement 5.

As before, if the walk from

v^{'}

v

is not a path, each pair of repeated vertices can be eliminated by “snipping out” the portion of the walk between them.

Statement 5 implies Statement 1.

Reverse the path from

v^{'}

v

to obtain a walk from

v

v^{'},

thereby satisfying the definition of connected vertices.

🔗

A nonconnected graph can be considered to simply be a collection of connected subgraphs.

connected component (working definition)

🔗

a connected subgraph of a graph which is not contained in any larger connected subgraph of that graph

connected component (formal definition)

🔗

a subgraph

G^{'}

of a graph

G

that satisfies the following:

🔗
$G^{'}$ is connected;
🔗
if $G^{″}$ is a subgraph of $G$ such that $G^{″}$ is connected and $G^{'} ⪯ G^{″},$ then $G^{″} = G^{'}$

🔗

Example 15.3.4. Breaking a nonconnected graph into connected components.

🔗

Considering Figure 15.3.5 below as a single graph, we have placed the connected components (of which there are three) into boxes.

A graph to map the possible paths in another graph. — Figure 15.3.5. A nonconnected graph as a collection of connected subgraphs.

🔗

This nonconnected graph has other connected subgraphs. For example, the subgraph that contains only the left-most two vertices joined by a single edge is a connected subgraph. But that connected graph is not a connected component because it is a subgraph of a larger connected subgraph.

🔗

Example 15.3.6. Connected components do not depend on how the graph is represented diagrammatically.

A nonconnected graph drawn with overlapping connected components. — (a) Overlapping connected components.

A nonconnected graph drawn with non-overlapping connected components. — (a) Overlapping connected components.

🔗

The two graphs in Figure 15.3.7 are in fact the same graph, just with different diagrammatic representations. In the second version of the graph, we have again identified connected components by placing each of them in a box.

🔗

Example 15.3.8. A connected graph has one component.

🔗

If a graph is connected, then the entire graph is a largest connected subgraph possible.

Figure 15.3.9. A connected graph with one connected component.

🔗

Note 15.3.10.

🔗

As in our working definition, informally the connected components of a graph

G

are the “largest” subgraphs of

G

that are connected. The second condition in the formal definition is just a positive way of stating the working definition. We will make the general notion of “largest” more precise in a similar way in Chapter 19 (see the definition of maximal element, the Test for Maximal/Minimal Elements, as well as Example 19.5.7).

🔗

Theorem 15.3.11. A lower bound for the number of edges in a connected graph.

🔗

G = (V, E)

is connected and

| V | = n,

then

| E | \geq n - 1 .

🔗

Proof.

By (strong) induction.

Base case $n = 1$ .

Every graph with only one vertex is connected and satisfies

| E | \geq 0 .

Induction step.

Assume

k \geq 1

and the statement is true for all

n \leq k .

Let

G = (V, E)

be a connected graph with

k + 1

vertices. We must show

| E | \geq k .

Arbitrarily choose some vertex

v_{0} \in V,

and let

G^{'} = (V^{'}, E^{'})

be the graph obtained from

G

by removing

v_{0}

and all edges incident to it. Unfortunately,

G^{'}

might not be connected. Let

G_{1}^{'}, \dots, G_{ℓ}^{'}

be its connected components. Write

G_{i}^{'} = (V_{i}^{'}, E_{i}^{'}),

and let

n_{i} = | V_{i}^{'} | .

Then each

G_{i}^{'}

is connected and has at most

k

vertices, so the induction hypothesis applies. Also note that

n_{1} + \dots + n_{ℓ} = k,

since every vertex of

G

except

v_{0}

is part of exactly one subgraph

G_{i}^{'} .

A depiction of removing one vertex from a graph. — (a) “Extra” vertex $v_{0}$ and the remaining subgraph $G^{'} .$

A depiction of removing one vertex from a graph and splitting remaining subgraph into connected components. — (a) “Extra” vertex $v_{0}$ and the remaining subgraph $G^{'} .$

Therefore, using our induction hypothesis we may calculate

\begin{aligned} | E | & = | E^{'} | + | {edges in G incident to v_{0}} | \\ = | E_{1}^{'} | + \dots | E_{ℓ}^{'} | + | {edges in G incident to v_{0}} | \\ \geq (n_{1} - 1) + \dots + (n_{ℓ} - 1) + | {edges in G incident to v_{0}} | \\ = k - ℓ + | {edges in G incident to v_{0}} | . \end{aligned}

However, since

G

is connected,

v_{0}

must be the glue keeping the subgraphs

{G_{i}^{'}}

together. That is, for each

i

there must be at least one edge between

v_{0}

and some vertex of

G_{i}^{'} .

Therefore,

\begin{aligned} | E | & \geq k - ℓ + | {edges in G incident to v_{0}} | \\ \geq k - ℓ + ℓ \\ = k . \end{aligned}

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 15.3 Connected vertices, graphs, and components

Example 15.3.1. A connected graph.

Example 15.3.2. A nonconnected graph.

Proposition 15.3.3. Characterizations of connected vertices.

Proof idea.

Statement 1 implies Statement 2.

Statement 2 implies Statement 3.

Statement 3 implies Statement 4.

Statement 4 implies Statement 5.

Statement 5 implies Statement 1.

Example 15.3.4. Breaking a nonconnected graph into connected components.

Example 15.3.6. Connected components do not depend on how the graph is represented diagrammatically.

Example 15.3.8. A connected graph has one component.

Note 15.3.10.

Theorem 15.3.11. A lower bound for the number of edges in a connected graph.

Proof.

Base case $n = 1$ .

Induction step.

Section 15.3 Connected vertices, graphs, and components

Example 15.3.1. A connected graph.

Example 15.3.2. A nonconnected graph.

Proposition 15.3.3. Characterizations of connected vertices.

Proof idea.

Statement 1 implies Statement 2.

Statement 2 implies Statement 3.

Statement 3 implies Statement 4.

Statement 4 implies Statement 5.

Statement 5 implies Statement 1.

Example 15.3.4. Breaking a nonconnected graph into connected components.

Example 15.3.6. Connected components do not depend on how the graph is represented diagrammatically.

Example 15.3.8. A connected graph has one component.

Note 15.3.10.

Theorem 15.3.11. A lower bound for the number of edges in a connected graph.

Proof.

Base case n=1.

Induction step.

Base case $n = 1$ .