dm2

graph consisting of vertices and edges conecting these vertices.

edges connecting the same verticies

graph having multiple edges connecting the same vertices

a graph the may include loos, and possibly even multiple edges connecting the same pair of vertices

• (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

a directed graph that has no loops or multiple directed edges

directed graphs that may have multiple directed edges from a vertex.

a graph with both directed and undirected edges

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

if e is associated with {u,v}, the edge e is called incident with the vertices u and v

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)

a vertex of degree zero

vertex of degree one

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

the vertext is called the inital vertex of (u,v) and v is called the termial vertex

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.

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

the complete graph on n vertices, denoted K_n, is the simple graph that contains exactly one edge between each pair of distinct vetices.

the cycle C_n, n>3, consists of n vertices v₁,v₂,...,v_n and edges {v₁,v₂}, {v₂,v₃},..., {v_n-1,v_n}, and {v_n,v}

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

a simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V₁ and V₂ such that every edge in the graph connects a vertex in V₁ and a vertex in V₂ (so that no edge in G connects either two vertices in V₁ or two in V₂) when this condition holds, we call the pair (V₁,V₂) a bipartite of the vertex set V of G.

• 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.

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

graphs G₁=(V₁,E₁) and G₂=(V₂,E₂) is the simple graph with vertex set V₁U V₂ and edge set E₁U E₂. The union of G₁ and G₂ is denoted by G₁U G₂

• 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.

an undirected graph has an even number of verices of odd degree.

• PROOF: let V₁ and V₂ 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.

• 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:

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:

a degree sequence with n>3 and d₁>1 is graphical if and only if (d₂-1, d₃-1,..., d_d1+1-1, d_d+2,..., d_n) is graphical.

• 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

• (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

• Let G=(V,E) be an undirected graph. Suppose that v₁,v₁,...,v_n are the vertices and e₁,e₂,...,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

the simple graph G₁=(V₁,E₁) and G₂=(V₂,E₂)are isomorphic if there is a one-to-one and onto function f from V₁ to V₂ with theproperty that a and b are adjacent in G₁ if and only if f(a) and f(b) are adjjacent in G₂, for all a and b in V₁. Such a function f is called an isomorphism.