graph theory 1

Simple graph

a graph with no multiple edges or loops

Multigraph

a graph with parallel edges

Subgraph

a graph whose vertices are all vertices of G and whose edges are all edges of G

Isomorphic

Graphs with one-one correspondence between the vertices of the graphs

Planar

a graph can be drawn in a way that no edges cross

Planar Drawing

a graph is drawn so that no edges cross

Face

a region bounded by a set of edges and vertices (in a planar graph)

Complete graph

a graph where each vertex is joined to each of the other vertices by exactly one edge

Null

a graph with no edges

Regular Graph

a graph with all vertices having the same degree

Face Regular

a planar graph where all faces have the same degree

Handshaking Theorem

Sum of degrees of vertices is twice the number of edges

Walk

a sequence of edges in which each edge shares a vertex with the previous edge

Connected

there exists a path between every pair of vertices

Bridge

an edge whose removal increases the number of connected components in a graph

Trail

a walk in which no edge (not vertex) is traversed more than once

Path

a walk in which no vertex (and edge) is visited more than once

Closed walk

a walk that starts and ends at the same vertex

Circuit

a closed trail

Cycle

a closed walk in which all vertices are distinct except for the first and last (basically a closed path)

Eulerian circuit

a circuit that traverses every edge in the graph

Hamiltonian cycle

a cycle that includes every vertex in the graph

Cycle graph

a connected graph consisting of one cycle in which every vertex has degree 2

Tree

A connected graph with no cycle

Forest

a graph (not necessarily connected), each of whose components is a tree

Leaf

a vertex of degree 1 in a tree

Spanning Tree

a subgraph of G that is a tree containing every vertex of tree