Definition talk:Vertex Deletion

I don't understand the need for the explains tag; as written the definition only applies to undirected graphs. If we want to extend this definition, we can, but currently it's just applying to graphs, not digraphs. Scshunt 23:46, 17 February 2012 (EST)

Good call - I have amended the definition so it specifically mentions that point. --prime mover 03:57, 18 February 2012 (EST)

I would say that a digraph should be a graph with extra structure; strictly formally this seems not to be the case at the moment, which would imply that there is no canonical forgetful functor from digraphs to graphs (i.e., a formal interpretation of 'forgetting' the direction of the arrows). However, I might be too influenced by axiomatic mathematics and rigorous set theory, and if this is the convention in literature (the paradoxical situation that a directed graph isn't a graph) it might be better to stick with it. Lastly, let it be noted that I generally haven't concerned myself with graph theory; it's just my perspective as a newcomer. --Lord_Farin 04:32, 18 February 2012 (EST)

At this stage of development it's useful to consider graphs (particularly not multigraphs) as a relation on a set of points: an undirected graph is equivalent to a symmetric relation, while a directed one loses this requirement. Alternatively, every undirected graph can be considered as a digraph with two arcs between each pair of connected vertices: one going one way and one going the other. So technically an undirected graph can be considered as a digraph with a constraint. Once we do functors and forgetfulness, your statement about that may become appropriate.

Mind you, I agree on this: in graph theory, while definitions can be appreciated in an intuitive way by describing their appearance in a depiction, in order to completely define an entity, we need to find a rigorous non-graphical definition, e.g. via matrices - but then the work of proving the various results becomes so much more unwieldy. --prime mover 06:04, 18 February 2012 (EST)

Matrices have the problem that they generally confine themselves to countable situations (mostly finite; the countable is already stretching it). I will try to concern my mind, which is as of yet unspoilt by convention, over it to try and think of an axiomatisation. --Lord_Farin 06:23, 18 February 2012 (EST)

There is no really natural way to associate them because the natural functor (association, mapping, whatever) from graphs to digraphs transforms an edge in a graph into a pair of edges in the corresponding digraph, one in each direction. But the underlying graph of a digraph contains an edge wherever there is an edge in either direction in the digraph.

It's also a much simpler treatment to go with edges as unordered pairs (sets of size 2). If you go with edges of a graph being defined in terms of a symmetric relation, then you can't really refer to "an edge" directly, and then any means you choose to refer to an edge is just really a more convenient definition of an edge. One other definition approach is similar to that of category theorists: a set of vertices and a set of edges, and a mapping from edges into V (in the case of a digraph, into V x V or two mappings, each into V). This seems like it would be more cumbersome than not, though.

(For the record, most of my knowledge in the area comes from courses at the University of Waterloo, not from books)