UBC Mathematics Department
http://www.math.ubc.ca
For graphs, we refer to the degree of a vertex as the number of edges in the graph incident with the vertex. Given a graph G=(V,E) we are often interested in finding a subgraph H=(V,E') of G (E' is a subset of E) which satisfies constraints on its degrees. For example a perfect matching in a graph corresponds to a subgraph all of whose degrees are 1.
A somewhat strange version of this is to consider 'subgraphs' where we are allowed to take an edge e a fractional amount x(e) with x(e) in the interval [0,1]. Such a choice for e contributes x(e) to the degrees at each endpoint of e. The problem of degree constrained subgraphs becomes much easier in this setting (becomes a network flow problem) but the answer is hardly interesting to graph theorists. So we must investigate ways that we can preserve the degree constraints while making x(e) either 0 or 1. These investigations have yielded fast algorithms, new existence theorems, a quick edge colouring heuristic, and graph decompositions.