Graph Theory/Nodes & edges

Basic Definitions

Graph

an ordered pair $(V,E)$:

• V is the vertex set, where the elements are vertices; often written as V(G)
• E is the edge set, where the elements are edges; often written as E(G)

Lines that intersect are (usually) ignored as irrelevant (see planarity for where intersections do matter)

Two graphs are considered equal when $V_1=V_2$ and $E_1=E_2$.

Order

the number of vertices in a graph, denoted $|V(G)|$, often using $n$

Size

the number of edges in a graph, denoted $|E(G)|$, often using $m$

Notice: the order of any graph must be at least 1 (n≥1).

• If $n=1$, the graph is considered trivial.
• If n≥2, the graph is considered nontrivial.