The user-friendly version of this content is available here.
The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.
This essential trains for: Math Kangaroo 5-6, Math Kangaroo 7-8, Math Kangaroo 9-10, AMC-10, AMC-12, AIME.
A graph is a set of objects that may be connected by links.
Two graphs are isomorphic (iso=equal, morphos=shape) if they have the same set of objects connected in the same ways. For example, the following two graphs are isomorphic:
The elements of the set are called the vertices of the graph.
The connectors are called edges.
A graph is connected if there is a path from any vertex to any vertex.
For instance, in the figure above, the vertex A can be reached from vertex D either by going to B, then to C or by going to F then to E.
An example of disconnected graph is the one in the figure below. This graph consists of two portions that cannot be reached from one another. We say that this graph is a disconnected graph consisting of two connected components. (Attention! Each component is a connected graph. The word 'connected components' does not mean they are connected to each other.)
The number of edges that are incident at a vertex is called degree of that vertex.
For instance, in the graph above, the vertex A has degree 2 and the vertex X has degree 1.
Vertices with even degree are called even vertices. Vertices with odd degree are called odd vertices.
An edge that has at least one vertex of degree 1, like the edge YX is called a pendant edge or a half-edge.
A cycle is a subset of edges that form a closed loop. A graph can have one or more cycles. Below is an example of cycles:
Observe the cycles: ABCDEF, ABCDF, and FED.
A graph that is connected but contains no cycles at all is called a tree.
Notice the presence of pendant edges in the tree.
A graph in which all vertices can be visited without lifting the pen and while using each edge only once, is called an Eulerian graph. Note that each vertex may be visited more than once.
A graph that can be drawn so that no two edges intersect each other is called planar.
See in the figure examples of planar graphs.
Graphs are important for the mathematical modeling of networks: friendships on social media, networks of devices (computers, phones), etc. More and more problems on math contests are based on graph theory so make sure you read all the essentials on this topic.