Scribd
Upload
5 views1 page

Graph Theory Problems and Solutions

The document contains a tutorial with various problems related to graph theory and tree structures. It includes proofs and algorithms for concepts such as tree degrees, BFS and DFS trees, binary trees, bridges in graphs, graph coloring, shortest cycles, and topological sorting. Each problem requires a demonstration of understanding and application of graph theory principles.

Uploaded by

viratkalshan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views1 page

Graph Theory Problems and Solutions

The document contains a tutorial with various problems related to graph theory and tree structures. It includes proofs and algorithms for concepts such as tree degrees, BFS and DFS trees, binary trees, bridges in graphs, graph coloring, shortest cycles, and topological sorting. Each problem requires a demonstration of understanding and application of graph theory principles.

Uploaded by

viratkalshan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

MTL342

Tutorial 3

1. Prove that every tree with maximum degree ∆ > 1 has at least ∆ vertices of degree 1.
2. Let G be a simple graph, and let T be a BFS tree of G. Consider a non-tree edge e = uv ∈ E(G)\E(T ).
At which levels of the BFS tree can the vertices u and v be located? How does this situation change
if T is instead a DFS tree?
3. A binary tree is a rooted tree in which each node has at most two children. Show that in any binary
tree with at least two vertices, the number of nodes with two children is exactly one less than the
number of leaves. Note that we do not consider the root as a leaf even if its degree is 1.

4. Given an undirected, connected graph G = (V, E), a bridge in the graph is an edge whose removal
would break the graph into two pieces. (In other words, a bridge is an edge e ∈ E such that G = (V, E)
is connected but G′ = (V, E − {e}) is disconnected.)
(a) Show that every bridge must appear in every spanning tree of the graph.
(b) Show that for any edge e, you can test whether e is a bridge or not in O(|E|) time.
(c) Design an algorithm that finds all bridges in G in O(|V | + |E|) time.
5. Consider an undirected graph G with n vertices and m edges. We want to assign each vertex one of
the two colors, red or blue, so that the endpoints of every edge receive different colors. Describe an
algorithm that runs in O(n + m) time to check whether such a coloring is possible, and if it is, output
one valid coloring.

6. Given an undirected graph G with n vertices and m edges, find the length of a shortest cycle in the
graph in O(n2 ) time.
7. Given an undirected graph G, find all the edges that lie on ANY shortest length path between a given
pair of vertices (u,v) (there could be multiple shortest length paths between a pair of vertices).

8. Given a tree rooted at r, determine the relationship between any two arbitrary vertices u and v
(ancestor/descendant/none)
9. Given a directed acyclic graph, describe an algorithm to find any topological sorting of the vertices.
(Topological sorting of vertices of a directed acyclic graph is a linear ordering/permutation of vertices
such that for every directed edge (u, v), vertex u comes before vertex v in the ordering.)

You might also like