Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory Question

  1. Dec 31, 2014 #1
    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.
  2. jcsd
  3. Dec 31, 2014 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    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:
  4. Dec 31, 2014 #3
    Ah ha! I was thinking of a graph as a set containing two sets. Thank you for the clarification!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook