# Field:Graph Theory

# Graph Theory

Graph theory is the study of **graphs**. A graph is informally a collection of points, known as vertices, connected by lines, known as edges.

For a more in depth but general discussion, look at the Graph Theory page.

[[Image:|300px|thumb|right|]] |

### Basic Terminology

- Acyclic graph- a graph which contains no cycles
- Adjacent - two vertices are said to be adjacent if an edge connects them.
- Cycle- A path for which the first element is the same as the final element
- Directed graph (or digraph)- a graph for which all edges are assigned a direction. That is, for an edge between an arbitrary vertex A and vertex B, assigning a direction means the edge is either directed towards vertex A or towards vertex B.
- Eulerian Circuit- A cycle which contains all of the edges of a graph. This idea was inspired by the the Seven Bridges of Königsberg problem.
- Hamiltonian Cycle- A cycle which contains all of a graph's vertices.
- Hamiltonian Path - A path which contains all of a graph's vertices.
- Path - A sequence of distinct graph edges
- Planar Graph - A graph that can be drawn such that no two edges overlap each other.
- Spanning Tree- a tree which contains all vertices of a graph.
- Tree- a connected, acyclic graph.
- Vertex Degree - the number of edges attached to a vertex (or node). Loops are counted twice.
- Walk- A sequence of adjacent graph vertices and edges such that each edge and vertex is distinct.

### Topics of interest

Topics of interest in graph theory, and some examples of questions posed in graph theory, include:

- Graph coloring- how many colors are needed to color a graph such that no adjacent vertices are the same color? (See the Four Color Theorem)
- Spanning trees- how many different spanning trees exist for a given graph? Given a weighted graph, what is the spanning tree of least total weight? (See Kruskal's Algorithm)
- How can we tell if a graph is cyclic or acyclic? Planar or non-planar?
- Isomorphism- When do two graphs have essentially the same structure?

And so on.

## Examples of Geometry

To see all Graph Theory related pages, head over to the Graph Theory category.

## References