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 1 Show 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.
A graph is connected if for every pair of vertices there exists a path between and . A tree is a connected acyclic graph.
Exercise 2 Prove 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.