In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, Veblen's theorem, introduced by , states that the set of edges of a finite
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
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 end ...
(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
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbe ...
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 ENDS may refer to:
End Mathematics
*End (category theory)
* End (topology)
* End (graph theory)
* End (group theory) (a subcase of the previous)
* End (endomorphism) Sports and games
*End (gridiron football)
*End, a division ...
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
Notes
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 t ...
, volume=14 , issue=1 , pages=86–94, doi = 10.2307/1967604
Theorems in graph theory