# graph

A *graph* $G$ is an ordered pair^{} of disjoint sets $(V,E)$ such that $E$ is a subset of the set ${V}^{(2)}$ of unordered pairs of $V$. $V$ and $E$ are always assumed to be finite, unless explicitly stated otherwise. The set $V$ is the set of *vertices* (sometimes called nodes) and $E$ is the set of *edges*. If $G$ is a graph, then $V=V(G)$ is the vertex set of $G$, and $E=E(G)$ is the edge set.
Typically, $V(G)$ is defined to be nonempty. If $x$ is a vertex of $G$, we sometimes write $x\in G$ instead of $x\in V(G)$.

An edge $\{x,y\}$ (with $x\ne y$) is said to *join* the vertices $x$ and $y$ and is denoted by $xy$. One says that the edges $xy$ and $yx$ are *equivalent ^{}*; the vertices $x$ and $y$ are the

*endvertices*of this edge. If $xy\in E(G)$, then $x$ and $y$ are

*adjacent*, or

*neighboring*, vertices of $G$, and the vertices $x$ and $y$ are

*incident*with the edge $xy$. Two edges are

^{}*adjacent*if they have at least one common endvertex. Also, $x\sim y$ means that the vertex $x$ is adjacent to the vertex $y$.

Notice that this definition allows pairs of the form $\{x,x\}$, which would correspond to a node joining to itself. Some authors explicitly disallow this in their definition of a graph.

Some graphs.

Note: Some authors include multigraphs^{} in their definition of a graph. In this notation, the above definition corresponds to that of a *simple graph*. A graph is then *simple* if there is at most one edge joining each pair of nodes.

Adapted with permission of the author from by Béla Bollobás, published by Springer-Verlag New York, Inc., 1998.

Title | graph |

Canonical name | Graph |

Date of creation | 2013-03-22 11:57:54 |

Last modified on | 2013-03-22 11:57:54 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 34 |

Author | mathcam (2727) |

Entry type | Definition |

Classification | msc 05C99 |

Related topic | LoopOfAGraph |

Related topic | NeighborhoodOfAVertex |

Related topic | EulersPolyhedronTheorem |

Related topic | Digraph^{} |

Related topic | Tree |

Related topic | SpanningTree |

Related topic | ConnectedGraph |

Related topic | Cycle |

Related topic | GraphTheory |

Related topic | GraphTopology |

Related topic | Subgraph^{} |

Related topic | SimplePath |

Related topic | EulerPath |

Related topic | Diameter3 |

Related topic | DistanceInAGraph |

Related topic | GraphHomomorphism |

Related topic | Pseudograph^{} |

Related topic | Multigraph |

Related topic | OrderOf |

Defines | edge |

Defines | vertex |

Defines | endvertex |

Defines | adjacent |

Defines | incident |

Defines | join |

Defines | vertices |

Defines | simple graph |