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:

    “Good gentlemen, look fresh and merrily.
    Let not our looks put on our purposes,
    But bear it as our Roman actors do,
    With untired spirits and formal constancy.”
    —William Shakespeare (1564–1616)

    “... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
    —George Eliot [Mary Ann (or Marian)