# Selected topics in finite mathematics/What is a graph

A graph is a collection of vertices, some of which may be connected by edges. Typically a vertex is represented by a circle or point; an edge would be represented by a line connecting the vertices.

## Objectives

The goal is to identify vertices and edges in a graph.

## Details

A graph is made up of edges and vertices. A graph is said to be connected if for every pair of its vertices, there is at least one path connecting the two vertices.

## Examples

1. Consider figure E1, the graph with vertices "A", "B", "C", "D", and "E". There are six directed edges connecting these vertices. Each edge has an accompanying weight. A path of weight 51 is E-A-C-D. A cycle of weight 42 is B-A-C-B.

## Nonexamples

1. Consider figure E1. In this graph E-A-B is not a path, because A-B is not an edge.

## FAQ

Q: What is a vertex?

A: Point

Q: What is an edge?

A: Lines connecting vertices, or points

## Homework

1. In figure H1, identify a vertex.
2. In figure H1, identify an edge and its corresponding weight.
3. In figure H1, find three different paths of total weight 8.
4. In figure H1, find a cycle of weight 15.
5. Redraw figure H1 so that vertex "H" is to the right of vertex "F"
6. Remove vertex "B" from figure H1. (When removing a vertex, you need to remove all incident edges as well)
7. Remove vertex "B" from figure H1, then find a cycle that uses all the remaining vertices.

## Homework Solutions

1. "A" is one of the vertices in figure H1. "B" is anther vertex, which is connected to all other vertices except "F".
2. A-C is one of the edges in figure H1. Weight is 5.
3. The paths C-A-B, E-C-F, and C-E-B-A each have a total weight of eight.
4. The cycle G-B-H has a weight of 15.