Let G be a simple graph. Prove that the connection relation in G is an equivalence...

Let G be a simple graph. Prove that the connection relation in G is an equivalence relation on V (G)

Solutions

Expert Solution

Theorem: Let G = (V, E) be a graph. Then the connectivity relation
over V is an equivalence relation.
Proof: Consider an arbitrary graph G = (V, E). We will prove that
the connectivity relation over V is refexive, symmetric, and
transitive.
To show that connectivity is refexive, consider any v ∈ V. Then
the singleton path v is a path from v to itself. Therefore, v is
connected to itself, as required.
To show that connectivity is symmetric, consider any x, y ∈ V
where x is connected to y. We need to show that y is connected
to x. Since x is connected to y, there is some path x, v₁, …, vₙ, y
from x to y. Then y, vₙ, …, v₁, x is a path from y back to x, so y is
connected to x.
Finally, to show that connectivity is transitive, let x, y, z ∈ V be
arbitrary nodes where x is connected to y and y is connected to
z. We will prove that x is connected to z. Since x is connected to
y, there is a path x, u₁, …, uₙ, y from x to y. Since y is connected
to z, there is a path y, v₁, …, vₖ, z from y to z. Then the path
x, u₁, …, uₙ, y, v₁, …, vₖ, z goes from x to z. Thus x is connected to z,as required.

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

let G be a simple graph. show that the relation R on the set of vertices...

let G be a simple graph. show that the relation R on the set of vertices of G such that URV if and only if there is an edge associated with (u,v) is a symmetric irreflexive relation on G

Prove that \strongly connected" is an equivalence relation on the vertex set of a directed graph

Prove that the equivalence classes of an equivalence relation form a partition of the domain of...

Prove that the equivalence classes of an equivalence relation form a partition of the domain of the relation. Namely, suppose ? be an equivalence relation on a set ? and define the equivalence class of an element ?∈? to be [?]?:={?∈?|???}. That is [?]?=?(?). Divide your proof into the following three peices: Prove that every partition block is nonempty and every element ? is in some block. Prove that if [?]?∩[?]?≠∅, then ???. Conclude that the sets [?]? for ?∈?...

Let X be a non-empty set and R⊆X × X be an equivalence relation. Prove that...

Let X be a non-empty set and R⊆X × X be an equivalence relation. Prove that X / R is a partition of X.

Let G be a simple graph. G is said to be maximal planar if it is...

Let G be a simple graph. G is said to be maximal planar if it is planar and the addition of any new edge to G results in a (simple) non-planar graph. Examples of maximal non-planar graphs are K4 , K5 minus an edge, and K3,3 minus an edge. (a) Show that a maximal planar graph is connected. (b) Show that a maximal planar graph of order ≥3 has no bridges. (c) Show that every face of a maximal planar...

Let G be a graph. prove G has a Eulerian trail if and only if G...

Let G be a graph. prove G has a Eulerian trail if and only if G has at most one non-trivial component and at most 2 vertices have odd degree

1) a) Let k ≥ 2 and let G be a k-regular bipartite graph. Prove that G...

1) a) Let k ≥ 2 and let G be a k-regular bipartite graph. Prove that G has no cut-edge. (Hint: Use the bipartite version of handshaking.) b) Construct a simple, connected, nonbipartite 3-regular graph with a cut-edge. (This shows that the condition “bipartite” really is necessary in (a).) 2) Let F_n be a fan graph and Let a_n = τ(F_n) where τ(F_n) is the number of spanning trees in F_n. Use deletion/contraction to prove that a_n = 3a_n-1 - a_n-2...

Prove that if G is a simple graph with |V (G)| = n even, where δ(G)...

Prove that if G is a simple graph with |V (G)| = n even, where δ(G) ≥ n 2 + 1, then G has a 3-regular spanning subgraph.

Let G be a simple planar graph with no triangles. (a) Show that G has a...

Let G be a simple planar graph with no triangles. (a) Show that G has a vertex of degree at most 3. (The proof was sketched in the lectures, but you must write all the details, and you may not just quote the result.) (b) Use this to prove, by induction on the number of vertices, that G is 4-colourable.

Let A be incidence matrix of graph G. prove if G has a cycle, then null...

Let A be incidence matrix of graph G. prove if G has a cycle, then null space of transpose of A is not {0} (there exists non-trivial solution of (A^T)y=0)

Subjects