Top Qs
Timeline
Chat
Perspective

Veblen's theorem

From Wikipedia, the free encyclopedia

Remove ads
Remove ads

In mathematics, Veblen's theorem, introduced by Oswald Veblen (1912), states that the set of edges of a finite graph can be written as a union of disjoint simple cycles if and only if every vertex has even degree. Thus, it is closely related to the theorem of Euler (1736) that a finite graph has an Euler tour (a single non-simple cycle that covers the edges of the graph) if and only if it is connected and every vertex has even degree. Indeed, a representation of a graph as a union of simple cycles may be obtained from an Euler tour by repeatedly splitting the tour into smaller cycles whenever there is a repeated vertex. However, Veblen's theorem applies also to disconnected graphs, and can be generalized to infinite graphs in which every vertex has finite degree.[1]

If a countably infinite graph G has no odd-degree vertices, then it may be written as a union of disjoint (finite) simple cycles if and only if every finite subgraph of G can be extended (by including more edges and vertices from G) to a finite Eulerian graph. In particular, every countably infinite graph with only one end and with no odd vertices can be written as a union of disjoint cycles.[1]

Remove ads

See also

Notes

Loading content...

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads