Keo's Notes

Simple Graphs

3 min read

Combinatorics

Definition

A (simple) graph is defined as a set of vertices and a set of edges which connect two vertices (undirected). And edge is written as , sometimes written as , where . Graphs must have no loops and two vertices can only be connected by a single edge. A finite graph is a graph with a finite number of vertices. The degree (also called order) denoted as of a vertex is the number of edges incident to it - the number of edges connect to it.

Properties

Explanations

    1. Start with a finite graph with no edges so
    2. Adding any edge has to connect two vertices and it will increase the order of each of those vertices by one increasing the sum by 2.
    1. Given a finite graph any vertex can be connected to at most all other vertices.
    2. For a graph with vertices, for all vertices , there are at most edges it can be connected so

Isomorphism

2 (simple) graphs are isomorphic if they have the same structure e.g. same number of vertices connected in the same way. Rigorously two graphs are isomorphic if there exists a function called a graph isomorphism that satisfy the following properties

  1. is Bijective

Subgraphs

A subgraph of is a graph each of whose vertices and edges belongs to .

Walks

A Walk is a route through a graph along the edges from one vertex to the next. A Path (denoted as ) is a walk where no vertex is visited more than once. A Trail is a walk in which no edge is visited more than once. A Cycle (denoted as ) is a walk in which the end vertex is the same as the start vertex but no other vertex is repeated more than once. (Basically a path that starts and ends at the same place, but strictly it is not a path as the star/end vertex is visited twice.) A Hamiltonian Cycle is a cycle that includes every vertex in a graph.

Connection

Two vertices are connected if there exists a path between them. A graph is connected if every vertex is connected. If it is not connected it is disconnected.

Complete Graph

A Complete Graph (denoted as ) is a graph in where every vertex is connected to every other vertex by an edge. It has edges.

Planar

A graph is planar if it can be drawn on a plane with no edges meeting/crossing over other than at the vertices.

Tree

A tree is a connected graph which contains no cycles. A spanning tree of a graph is a subgraph which contains all the vertices in and is also a tree.

Graph View

Backlinks