Graph Theory (Discrete Mathematics)

Definitions and theorems that you need to know

Define a walk

A set of edges joined end to end so that the end vertex of one edge is the start vertex of the next

Define a trail

A walk in which no edges are repeated, although vertices can be repeated

Define a cycle

A trail that starts and finishes at the same vertex and in which no vertices are repeated

What is a connected graph?

A graph in which it is possible to get from any vertex to any other vertex

What is a loop?

An edge that connects a vertex to itself

What is a multiple edge

When 2 or more edges connect the same pair of vertices

What is a simple graph?

A graph with no loops or multiple edges

What is the degree of a vertex?

The number of edges that end at that vertex

What is a subgraph?

A graph formed by using some or all the edges and some or all of the vertices, meaning it is contained within another graph.

What is a subdivision?

Inserting a vertex of degree 2 into an edge

What is a complete graph?

Every vertex is connected by a single edge to every other vertex. Denoted K_n and has 0.5n(n-1) edges

Define a bipartite graph

A graph that can be partitioned into 2 sets so that every edge joins a vertex from one of these sets to a vertex in the other set.

What is a complete bipartite graph?

A simple bipartite graph with the maximum possible number of edges. It has mn edges where m and n give the number of edges in each set.

What is an adjacency matrix?

Shows the number of edges that directly connected each pair of vertices.

What is the complement of a simple graph?

The set of edges that when added to a graph, makes a complete graph.

What is a tree?

A simple-connected graph with the minimum possible number of edges. If it has n vertices it will have n-1 edges.

What is a traversable graph?

A graph that can be drawn as a trail without repeating an edge twice.

Define an eulerian graph

A traversable graph in which the trail starts and finishes at the same vertex. Every vertex has an even degree

Define a semi-eulerian graph

A connected graph that has exactly 2 odd vertices. These graphs are traversable but the trail starts at one odd vertex and finishes at the other.

Define an hamiltonian graph

Contains a cycle that passes through every vertex exactly once apart from finishing at the same vertex.

Define a planar graph

A graph that can be drawn so that no edges cross

What is euler’s formula for a connected planar graph?

V - E + F = 2

What is Kuratowski’s Theorem?

A necessary and sufficient condition for a finite graph to be planar is that it does not contain K5 or K3,3

What does it mean for 2 graphs to be isomorphic?

2 graphs are isomorphic if they have the same structure. This can be shown by setting up a correspondence between the 2 sets of vertices.