Which of the following are always true: A weighted, undirected graph has at leas

Question

Which of the following are always true:

A weighted, undirected graph has at least one spanning tree.

A directed graph cannot have exactly three vertices of odd out-degree.

All forests can be colored with 2 colors.

Consider a minimum spanning tree T in a graph G. if the weight of an edge of T is decreased, then the resulting tree is still a minimum spanning tree.

There are binary search trees of 15 distinct integers that are also binary max-heaps.

If every vertex in a graph has degree 1 or 2, the graph is planar.

Explanation / Answer

A weighted, undirected graph has at least one spanning tree--- true

A directed graph cannot have exactly three vertices of odd out-degree - true as it can have 2 at max

All forests can be colored with 2 colors -true as forest is 6 vertices and 5 edges

if the weight of an edge of T is decreased, then the resulting tree is still a minimum spanning tree.---true as the edge was already the part of the min spanning tree which means its value was already less so reducing it further will reduce the cost further and the edge will obviously be presdent in the min spanning tree.

If every vertex in a graph has degree 1 or 2, the graph is planar.--- true

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.