A

A connected graph is in one piece. If a graph has several pieces it is called disconnected and each piece is called a component of the graph.

Below: G is a connected graph, while H is a graph with 4 components.

Intuitively, sets fail to be convex because they have either notches or holes.

(The polygon above has two notches and is non-convex.)

(The region lying between the pentagon and the triangle is non-convex since the region has a hole in it.)

Graph

Examples of simple graphs are shown below:

Quadrilateral

Quadrilaterals can be either convex or non-convex. Furthermore, there are many special kinds of quadrilaterals one can mention: parallelograms, rhombuses, squares, rectangles, trapezoids, etc.

A polygon is an alternating sequence of points (called the vertices of the polygon) and line segments (called the edges or sides of the polygon) where the last segment has an endpoint coinciding with the first point in the sequence. We do not allow these line segments to pass through previous vertices of the polygon. However, the line segments are allowed to intersect each other at points other than the vertices. Polygons where this does not happen are known as simple. Usually we insist that the whole structure lies in a single plane. A polygon with n vertices is called an n-gon. The names triangle, quadrilateral, pentagon, and hexagon are used to describe polygons with 3-6 edges, respectively.

The diagram below shows a 6-gon or hexagon. This hexagon is not convex.

The diagram below shows a non-simple hexagon.

If all the edges of a polygon have the same length the polygon is called equilateral. If the angles between consecutive sides of a polygon are the same then the polygon is called equiangular. A polygon which is both equiangular and equilateral is called regular. Note that rectangles are equiangular but they do not have to be equilateral.

The 4-gon below is equiangular but not equilateral.

The 4-gon below is equilateral but not equiangular:

The diagram below shows a non-simple but regular pentagon:

The diagram below shows a convex regular pentagon:

A polyhedron is a surface made up of a finite number of flat (plane) pieces. Some polyhedra may go off to infinity and others are bounded, that is, they will fit inside a large sphere. A tetrahedron is an example of a bounded polyhedron,

The diagram below shows an example of an unbounded polyhedron. The three rays that emanate from H go off to “infinity.”

The most familiar polyhedra in 3-dimensional space are those where the flat pieces do not intersect each other and where the surface formed is like a sphere. Such polyhedra can be either convex or non-convex. Branko Grünbaum introduced the word polytope to mean a bounded convex polyhedron.

Polyhedra exist in spaces of all dimensions. Thus, one can speak of polyhedra in 3-space or 18-dimensional space. The analog of a polyhedron in 2-dimensions is a polygon; it is made up of line segments.

Sometimes it is convenient to think of a polyhedron as a “solid,” that is, it includes the points both on the surface and the interior of the surface. However, usually when one refers to a polyhedron one means the surface itself, and if one wants to make note of the points within the polyhedron, one refers to the polyhedron and its interior.

Three-dimensional polyhedra can be thought of as being assembled from two-dimensional polygons. These polygons are referred to as the faces of the polyhedron.

In the diagram below, the graph G is shown and a spanning tree is shown in thick red lines.

If a graph G has |V| vertices, then the number of edges in any spanning tree of G is |V| -1.

A sample of five trees is shown below:

Trees have many nice properties:

There are unique paths between any two vertices.

The number of vertices is one more than the number of edges.

The removal of an edge disconnects the tree.

A tree with at least one edge contains at least two vertices of valence 1.

The valence of a vertex in a simple graph is the number of edges at the vertex. If a graph has loops, the loop contributes 2 to the valence of the vertex.

For the (simple) graph below: vertices c and e have valence 1, vertex g has valence 2, vertices a, b, and f have valence 3, and vertex d has valence 5.

Another name for the valence of a vertex is the degree of a vertex. Computer scientists usually call vertices of a tree which are 1-valent “leaves.”