Graph Theory

Basic vocab and knowledge to grind for graph theory

Connected Component

A subgraph of a graph G is a connected component if it is the maximal connected subgraph.

Handshake Lemma

In any graph the sum of the degrees of all vertices is twice the number of edges.

Walk

A walk is an alternating sequence of vertices and edges. Imagine walking over that sequence.

Trail

A trail is a walk in which all edges are distinct.

Circuit

A circuit is a trail with the same start and end point.

Path

A path is a walk where all vertices are distinct.

Cycle

A cycle is a path that starts and ends at the same point.

Eulerian Circuit

An eulerian circuit is a cycle around a graph which uses each edge exactly once and starts and ends at the same point. If a graph has an eulerian circuit then it is eulerian.

Condition for Eulerian Circuit

In an undirected multigraph, if all degrees are even then there exists a eulerian circuit.

Eulerian trail

A trail which visits each edges exactly once.

Condition for an eulerian trail

An eulerian trail exists iff G is connected and contains 0 or 2 vertices of odd degree.

Hamiltonian Cycle

A cycle in G which visits each vertex exactly once

Hamiltonian Path

A path in G which visits each vertex exactly once.

Condition for Hamiltonian Cycle

Suppose G is a graph with the degree of each vertex being at least n/2 rounded down. Then G contains a Hamiltonian cycle.

Subgraph

G contains a subgraph H if we can get from G to H by deleting edges and vertices.

Induced Subgraph

G contains an induced subgraph H if we can get to H from G by only deleting vertices.

Complete Graph

A complete graph on n vertices has all possible edges between n vertices (all n choose 2 of them).

Clique Number

The clique number of a graph is the number of the largest complete graph that is a subgraph of it.

Bipartite Graphs

A graph is bipartite if its vertices can be placed into two sets with no two vertices in the same set having an edge between them. These sets can be empty.

Coloring of a bipartite graph

All bipartite graphs are 2 colorable.

Complete Bipartite graph

A complete bipartite graph has all possible edges between the two sets.

Brook’s Theorem

If a graph G is not an odd cycle or a complete graph, its chromatic number is less than or equal to its maximum degree. If a graph G contains an odd cycle or a complete graph, its chromatic number is less than or equal to its maximum degree + 1.

Does clique number provide a bound for chromatic number?

NOOOOOOOOOOOOOOOOOO

Tree

A connected graph with no cycles is called a tree.