## You are here

Homegraph

## Primary tabs

# 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\neq 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 *Modern Graph Theory* by Béla Bollobás, published by Springer-Verlag New York, Inc., 1998.

## Mathematics Subject Classification

05C99*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Attached Articles

## Corrections

loops by archibal ✓

change one word by Mathprof ✓

Typos? by rm50 ✓

missing cached output by CWoo ✓