Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the category of finite graphs with graph homomorphisms as morphisms.

Are there interesting graph properties that can be defined in categorical language? Can for example connectedness be defined in categorical language?

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Disjoint union is the coproduct in the category of finite graphs, so connected graphs are precisely the noninitial objects in this category that can not be expressed as a coproduct of two nonempty subobjects. See the entry on connected object in the nlab.

If you want to read more about arguments that intertwine classical results in graphs theory with category theory I suggest the book "Graphs and homomorphisms" by J. Nesetril.

share|improve this answer
add comment

There are some subtle point concerning the definition of this category. It has different properties if you define "graph" in a different way.

If you allow your graphs to have loops, then the category of all graph becomes a topological category over SET. In particular all (small) limits and colimits exist in this category. Sometimes it is best to consider only the graphs with loops at all vertices (if you just don't draw them this subcategory can be identified with the category of all simple graphs). The product in this category is the tensor product of graphs. A connected object (in a topological category an object is connected if all morphisms into discrete objects are constant) in this category is exactly a connected graph.

The subcategory of graphs without loops is not that well behaved from the point of view of category theory, But graphs without loops have their merits too: A graph morphism from $(V,E)$ to the complete graph without loops on $n$ vertices is the same thing as a $n$-vertex-coloring of $(V,E)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.