Individual exercise: Girth. The girth of a graph G is the length of the shortest cycle...

Transcribed Image Text:

Individual exercise: Girth. The girth of a graph G is the length of the shortest cycle in G, and it is infinity if G is acyclic¹. Notice that the length of a cycle refers to the number of edges in it. (a) (2p.) Prove that an undirected unweighted graph G = (V, E) of girth strictly larger than t + 1 has no proper subgraph that is a t-spanner. ¹Since we are considering undirected graphs, acyclic means that G is a tree. (b) (3p.) Suppose that the edges are sorted in a non-decreasing order according to their weights, i.e., the greedy algorithm iterates over the edges in the sorted order. Prove that the output of Algorithm 1 has girth at least t + 1. Individual exercise: Girth. The girth of a graph G is the length of the shortest cycle in G, and it is infinity if G is acyclic¹. Notice that the length of a cycle refers to the number of edges in it. (a) (2p.) Prove that an undirected unweighted graph G = (V, E) of girth strictly larger than t + 1 has no proper subgraph that is a t-spanner. ¹Since we are considering undirected graphs, acyclic means that G is a tree. (b) (3p.) Suppose that the edges are sorted in a non-decreasing order according to their weights, i.e., the greedy algorithm iterates over the edges in the sorted order. Prove that the output of Algorithm 1 has girth at least t + 1.

Answer rating: 100% (QA)

la Consider any edge UV EF IF uv is removed from Go then do 1 changes from I to one ley than the le... View the full answer