minimally_connected.py

"""
This problem was asked by Facebook.

A graph is minimally-connected if it is connected and there is no edge that can be removed while still leaving the graph connected. For example, any binary tree is minimally-connected.

Given an undirected graph, check if the graph is minimally-connected. You can choose to represent the graph as either an adjacency matrix or adjacency list.
"""


def minimally_connected(graph):
    n = len(graph)
    num_edges = 0
    for v, edges in graph.items():
        num_edges += len(edges)
    num_edges //= 2
    return n - 1 == num_edges