Graph Theory Question

  • #1

Main Question or Discussion Point

So as I was beginning to read through my Graph Theory textbook I had a burning question I wanted to get some perspective on.

So a Graph is defined as an object containing a Vertex Set and an Edge Set,

v = # of elements in the vertex set and e = # of elements in the Edge Set (if any)

Would this mean that |g| = v + e = cardinality of the graph?

Abstract thinking is strange to me sometimes and its weird to think of a graph technically having cardinality.
 

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,013
1,235
Would this mean that |g| = v + e = cardinality of the graph?
If a graph were a single set expressed as the union of two sets, you could infer that "cardinality of the graph" was the cardinality of that single set. However a graph is defined to have a pair of sets, vertices and edges. It is not defined as the union of those two sets. So if we want to talk about the "cardinality of a graph" we must create a special definition for it.

These folks say that the cardinality of a graph is customarily defined as the cardinality of its set of vertices:
http://math.stackexchange.com/questions/442843/a-cardinality-of-a-graph
 
  • #3
Ah ha! I was thinking of a graph as a set containing two sets. Thank you for the clarification!
 
Top