Degree-constrained Spanning Tree - Formal Definition

Formal Definition

Input: n-node undirected graph G(V,E); positive integer k ≤ n.

Question: Does G have a spanning tree in which no node has degree greater than k?

Read more about this topic:  Degree-constrained Spanning Tree

Famous quotes containing the words formal and/or definition:

    “Then the justice,
    In fair round belly with good capon lined,
    With eyes severe and beard of formal cut,
    Full of wise saws and modern instances;
    And so he plays his part.”
    —William Shakespeare (1564–1616)

    “It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
    —Jane Adams (20th century)