Definition:Graph (Graph Theory)

From ProofWiki
Jump to navigation Jump to search

This page is about Graph in the context of Graph Theory. For other uses, see Graph.

Definition

A graph is intuitively defined as a pair consisting of a set of vertices and a set of edges each with a vertex at each end.


Vertex

Let $G = \struct {V, E}$ be a graph.

The vertices (singular: vertex) are the elements of $V$.

Informally, the vertices are the points that are connected by the edges.


Edge

Let $G = \struct {V, E}$ be a graph.

The edges are the elements of $E$.


Order

Let $G = \struct {V, E}$ be a graph.

The order of $G$ is the cardinality of its vertex set.


Size

Let $G = \struct {V, E}$ be a graph.

The size of $G$ is the count of its edges.


Notation

Let $G$ be a graph whose order is $p$ and whose size is $q$.

Then $G$ can be referred to as a $\tuple {p, q}$-graph.


A wider category: a graph whose order is $n$ can be referred to as an $n$-graph.


Also presented as

While it is commonplace to present a graph as a diagram consisting of dots connected by lines, some sources use circles for the vertices.

In that way, the labels for the vertices can be written neatly inside the circles.


Examples

Arbitrary Example 1

ExampleOfGraph.png


Arbitrary Example 2

Graph-2.png


Also see


  • Results about graphs can be found here.


Also defined as

Many treatments of this subject require that $V$ is non-empty, and so do not recognise the concept of a null graph.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Graph_(Graph_Theory)&oldid=612430"