Show that a graph with at least 2k vertices is k-connected if and
only if for...
Show that a graph with at least 2k vertices is k-connected if and
only if for any two unrelated subsets X, Y of V, such that | X | =
k = | Y |, there are k foreign paths between X and Y.
Solutions
Expert Solution
since, a graph is k connected if and only if it has k disjoint
paths joining two arbitrary vedrtex sets say X and Y of size k each
of many to many typeof which a vertex belongs to both the sets is
valid as one vertex path.
Given a connected graph G with n vertices. We say an edge of G
is a bridge if the graph becomes a disconnected graph after
removing the edge. Give an O(m + n) time algorithm that finds all
the bridges. (Partial credits will be given for a polynomial time
algorithm.) (Hint: Use DFS)
Let k be an integer satisfying k ≥ 2. Let G be a connected graph
with no cycles and k vertices. Prove that G has at least 2 vertices
of degree equal to 1.