# Selected topics in finite mathematics/What is a graph

Jump to navigation
Jump to search

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[edit | edit source]

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

## Details[edit | edit source]

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[edit | edit source]

- 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[edit | edit source]

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

## FAQ[edit | edit source]

**Q:** What is a vertex?

**A:** Point

**Q:** What is an edge?

**A:** Lines connecting vertices, or points

## Homework[edit | edit source]

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

## Homework Solutions[edit | edit source]

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