This will be a standard post that I will refer to when writing new blog posts as I get more into research topics. This particular page will contain information about graphs, and will be added as more information is needed.

A *graph* is a 2-tuple where is a finite set of *vertices*, and is a finite set of *edges*. Each edge is an unordered pair of vertices; if we instead consider each edge as an ordered pair of vertices, we get a *directed graph*, whereas the original definition is usually called an *undirected graph*. A *subgraph* of a graph is a subset of both ‘s vertices and edges. An *induced subgraph* is a subgraph and has every edge’s endpoints both defined in the subset of the vertices.

A *hyperedge* is defined similarly to a normal edge but instead is an (un)ordered tuple on a subset of the vertices. A *hypergraph* then is a graph that contains hyperedges. Normally we won’t talk about hypergraphs on this blog, but they certainly have many applications for where they are used, and are a nice generalization of the standard graph definition.

Two edges are *parallel* if they share the same endpoints, and a *multigraph* is a graph with (possibly) parallel edges.

**1. Example Graphs **

The *complete graph* on vertices, , is the graph where .

The *path graph* on vertices , , is the graph with edges .

The *cycle graph* on vertices , , is the graph with edges .

**2. More Definitions **

We say that two vertices are *adjacent* if they share the same endpoints. A *path* is a finite sequence of vertices in which and are adjacent for all (Note: there may be additional vertices in the middle of the sequence that are also equal).

A *cycle* in a graph is path (as defined above) in which . A graph is *acyclic* if it does not contain a cycle.

A graph is *bipartite* if there is a partition of the vertices such that all edges are in .

Exercise 1Show that a graph is bipartite if and only if it does not contain any odd-length cycles.

A *-clique* in a graph is a complete subgraph of on vertices.

** 2.1. Trees **

A graph is *connected* if for every pair of vertices there exists a path between and . A *tree* is a connected acyclic graph.

Exercise 2Prove that any tree on vertices has exactly edges.

A *connected component* of a graph is a subset of the vertices such that every two vertices have a path between them. A *forest* is a union of (possibly disjoint) trees.