graph consisting of vertices and edges conecting these vertices.
multiple edges
edges connecting the same verticies
multigraph
graph having multiple edges connecting the same vertices
pseudograph
a graph the may include loos, and possibly even multiple edges connecting the same pair of vertices
directed graph
(digraph)
a graph (V,E) that consist of a non-empty set of vertices (V) and a set of directed edges (E). Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u,v) is said to start at u and end at v
simple directed graph
a directed graph that has no loops or multiple directed edges
directed mulitgraph
directed graphs that may have multiple directed edges from a vertex.
mixed graph
a graph with both directed and undirected edges
adjacent
two vertices u and v in an undirected graph G are called adjacent (neighbors) in G if u and v are endpoints of an edge of G
incident
if e is associated with {u,v}, the edge e is called incident with the vertices u and v
degree of a vertex in an undirected graph
the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex, the degree of the vertex v is denoted deg(v)
isolated vertex
a vertex of degree zero
pendant vertex
vertex of degree one
adjacent to/from a vertex
when (u,v) is an edge of a graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u
initial/terminal vertex
the vertext is called the inital vertex of (u,v) and v is called the termial vertex
in-degree
in a graph with directed edges, the in-degree of a vertex v, denoted deg^{-}(v), is the number of edges with v as their teminal vertex.
out-degree
in a graph with directed edges, the out-degree of a vertex v, denoted deg^{+}(v), is the number of edges with v as their inital vertex
complete graph
the complete graph on n vertices, denoted K_{n}, is the simple graph that contains exactly one edge between each pair of distinct vetices.
cycle
the cycle C_{n}, n>3, consists of n vertices v_{1},v_{2},...,v_{n} and edges {v_{1},v_{2}}, {v_{2},v_{3}},..., {v_{n-1},v_{n}}, and {v_{n},v}
wheel
we obtain the wheel W_{n} when we add an additional vertex to the cycle C_{n}, for n>3, and connect this new vertex to each of the n vertices in C_{n} by new edges
bipartite graph
a simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V_{1} and V_{2} such that every edge in the graph connects a vertex in V_{1} and a vertex in V_{2 }(so that no edge in G connects either two vertices in V_{1} or two in V_{2}) when this condition holds, we call the pair (V_{1},V_{2}) a bipartite of the vertex set V of G.
complete bipartite graph
denoted K_{m,n}
the graph that has its vertex set partitioned into 2 subsets of m and n vertices, repectively. There is an edge between two vetices if and only if one vertex is is the first subset and the other vertex is in the second vertex.
subgraph of a graph
a subgraph of a graph G=(V,E) is a graph H=(W,F), where WcV and FcE. A subgraph H of G is a proper subgraph of G if H / G
union of 2 simple graphs
graphs G_{1}=(V_{1},E_{1}) and G_{2}=(V_{2},E_{2}) is the simple graph with vertex set V_{1}U V_{2} and edge set E_{1}U E_{2}. The union of G_{1} and G_{2} is denoted by G_{1}U G_{2}
Handshaking Theorem
Let G=(V,E) be an undirected graphwith e edges. Then,
2e = Σ_{v=V} deg(v)
PROOF: each edge is incident with 2 vertices. when we add up the degrees, each edge will get counted twice. Thus, our sum will be twice the number of edges.
Theorem 2
an undirected graph has an even number of verices of odd degree.
PROOF: let V_{1} and V_{2} be the set of vertices of even degree and the set of vertices of odd degree, repectively, is an undirected graph G=(V,E). Then,
2e = Σ_{v=V} deg(v) = Σ_{v=V1} deg(v) + Σ_{v=V2 }deg(v)
we know Σ_{v=V} deg(v) is even so the Σ_{v-v2} deg(v) must be even also to get 2e.
The only way add numbers sum to an even number is if there is an even number if them.
Theorem 3
Let G=(V,E) be a graph with directed eged. Then,
Σ_{v=V} deg^{-}(v) = Σ_{v=V }deg^{+}(v) = |E|
sum of terminal degrees = sum of initial degrees = edges
PROOF:
Theorem 4
a simple graph is bipartite is and only if it is possible to assign one of two different colors to each vertex of the graoh so that no two adjacent veritces are assignes the same color.
PROOF:
Havel/Hakimi
a degree sequence with n>3 and d_{1}>1 is graphical if and only if (d_{2}-1, d_{3}-1,..., d_{d1+1}-1, d_{d+2},..., d_{n}) is graphical.
adjacency list
another way to represent a graph with no multiple edges
A----B
| .. \ .. |
C----D
vertex | adj. vertices
A | B, C, D
B | A, D
C | A, D
D | A, B, C
adjaceny matrix
(or A_{G}) of G with repsect to the listing of the vertices is an nxn matrix zero-one matrix with i as its (i,j)thentry with V_{i} is adjacent to V_{j} and 0 as its (i,j)th to entry when V_{i }and V_{j} are not adjacent.
a_{ij} = {1 _{}if {Vi,Vj} is an edge of G
^{. . . .} {0 other wise
Incidence Matrix
Let G=(V,E) be an undirected graph. Suppose that v_{1},v_{1},...,v_{n} are the vertices and e_{1},e_{2},...,e_{n }are the edges of G. The the incidence matrix with repsect to this ordering of V and E is the nxn matrix M=[m_{ij}] where
m_{ij}={1 when edge e_{j} is incident with v_{i}
. . . { 0 other wise
Isomorphic Graph / Isomorphism
the simple graph G_{1}=(V_{1},E_{1}) and G_{2}=(V_{2},E_{2})are isomorphic if there is a one-to-one and onto function f from V_{1} to V_{2} with theproperty that a and b are adjacent in G_{1} if and only if f(a) and f(b) are adjjacent in G_{2}, for all a and b in V_{1}. Such a function f is called an isomorphism.