*Kiddle Encyclopedia.*

# Graph (mathematics) facts for kids

In graph theory a **graph** is used to represent the connection between two sets. One of the sets contains nodes (which are officially called **vertices**), the other one contains the connections (which are officially called **edges**). There are two classes of graphs, which are distinguished by the nature of the edges. Some edges can be travelled in both directions, other can only be travelled in one direction. Edges that can be travelled in one direction only are called *directed*, and the graph is called a *directed graph* or *digraph*. The ones which do not have a direction are called *undirected*, and the graph is called an *undirected graph*. If two vertices are connected by an edge, they are called *adjacent*.

The **order** of a graph, written as , is given by the number of vertices. A graph's **size** is , the number of edges. The **degree** of a vertex is the number of edges that connect to it, where an edge that connects to the vertex at both ends (a loop) is counted twice.

Vertices or edges may have weights. In general, weigts are used to show the costs associated with using the respective vertex or edge. In a graph that shows the cities of a region, the cost associated with a vertex may be the distance between two cities, or the amount of time it takes to travel between the two.

A graph were there is more than one edge between two vertices is called **multigraph**, one where there is at most one edge is called a **simple graph**. A **loop** is an edge that connects to the same vertex. Loops are only allowed in multigraphs.

A simple graph, where every vertex is directly connected to every other is called **complete graph**.

A sequence of vertices where two vertices which are next to each other in the sequence are connected by an edge is called a **path**.

A path which starts and ends at the same edge is called a **cycle**. The directed graph below with a cycle has the paths *BCEDB, CEDBC, EDBCE andDBCED* which are cycles.