Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does a graph with $0$ vertices count as a simple graph?

Or does a simple graph need to have a non-empty vertex set?

Thanks!

share|improve this question
2  
That would really depended on the definition you're using on your course, book or whatever. Sometimes authors don't even consider the "empty graph" to be a graph, in that case it can't be a simple graph. –  Git Gud Jan 13 '13 at 1:55

2 Answers 2

up vote 1 down vote accepted

It is typical to refer to a graph with no vertices as the null graph. Since it has no loops and no parallel edges (indeed, it has no edges at all), it is simple.

That said, if your present work finds you writing "Such and such is true for all simple graphs except the null graph", then it could be a good idea to announce at the beginning of your document that you will not consider the null graph to be simple.

share|improve this answer
    
The term empty graph is also very often applied to graphs with no edges and a positive number number of vertices. –  Chris Godsil Jan 14 '13 at 19:31
    
@ChrisGodsil Thank you for the remark. It seems the more common term for a zero-vertex graph is "null graph". I've corrected this in my answer. –  Austin Mohr Jan 14 '13 at 19:51

By wikipedia:

Simple graph

As opposed to a multigraph, a simple graph is an undirected graph that has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices. In a simple graph the edges of the graph form a set (rather than a multiset) and each edge is a distinct pair of vertices. In a simple graph with n vertices every vertex has a degree that is less than n (the converse, however, is not true — there exist non-simple graphs with n vertices in which every vertex has a degree smaller than n).

It satisfies all conditions, so, it should be.

share|improve this answer

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.