In mathematics, Veblen's theorem, introduced by , 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 that a finite graph has an
Euler tour
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...
(a single non-simple cycle that covers the edges of the graph) if and only if it is
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
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 graph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
s in which every vertex has finite degree .
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
End, END, Ending, or variation, may refer to:
End
*In mathematics:
** End (category theory)
** End (topology)
**End (graph theory)
** End (group theory) (a subcase of the previous)
**End (endomorphism)
*In sports and games
**End (gridiron footbal ...
and with no odd vertices can be written as a union of disjoint cycles .
See also
*
Cycle basis
In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be exp ...
*
Cycle double cover conjecture
*
Eulerian matroid
In matroid theory, an Eulerian matroid is a matroid whose elements can be partitioned into a collection of disjoint circuits.
Examples
In a uniform matroid U^r_n, the circuits are the sets of exactly r+1 elements. Therefore, a uniform matroid is ...
References
*. Reprinted and translated in .
*.
*{{Citation , last1=Veblen , first1=Oswald , author1-link=Oswald Veblen , title=An Application of Modular Equations in Analysis Situs , jstor=1967604 , series=Second Series , year=1912 , journal=
Annals of Mathematics
The ''Annals of Mathematics'' is a mathematical journal published every two months by Princeton University and the Institute for Advanced Study.
History
The journal was established as ''The Analyst'' in 1874 and with Joel E. Hendricks as the ...
, volume=14 , issue=1 , pages=86–94, doi = 10.2307/1967604
Theorems in graph theory