Graph Theory/Nodes & edges

From Wikibooks, the open-content textbooks collection

This book has been created on 19 June 2009, and still is under heavy construction. Content that is added is likely to be moved/deleted/edited significantly in a short amount of time. All wikibookians with knowledge in this subject are welcome to help out. You can remove this tag when the book has become more mature.

Contents 1 Basic Definitions

[edit] 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₁ = V₂ and E₁ = E₂.

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.]