Discrete 2 Graph Theory

definitions for graph theory quiz (profs. old notes ver.)

End vertices

Two vertices v1 and v2 are __ of e1

Parallel Edges

edges that have the same end vertices are called __

Loop

an edge of the form (v,v) is called a __

Simple Graph

A graph without any loops or parallel edge is called __

Empty Graph

A graph with no edges is called __

Null Graph

a graph with no vertices is called a __

Trivial Graph

a graph with only one vertex is called a __

Adjacent Edges

Edges that share the same vertex are called __

Adjacent Vertices

Two vertices u & v that share an edge are called __

Degree of a vertex

The __, written as d(v), is the # of edges with v as an end vertex. (by convention we count loop twice)

Pendant vertex

A vertex with degree 1 is called __

Pendant edge

An edge that has a Pendant vertex as an end point, is a __

Isolated vertex

A vertex whose degree is 0 is called __

Complete Graph(K_n)

every vertex is connected to every other vertex; degree sequence: n-1, n-1, n-1, … (n times)

Cycle Graph(C_n)

the vertices of the graph form a cycle; degree sequence: 2, 2, 2, … (n times)

Wheel Graph(W_n)

C_n, with an additional central vertex connected to all of the cycle vertices; degree sequence: n, 3, 3, 3 … (repeat 3, n times)

Complementary Graph

If we have a simple graph G, the __ is G’ is the graph where we have edges between vertices which don’t occur in graph G and vice versa.

The Union of simple graph G and its complementary graph G’

K_n

Bipartite Graph

A simple graph G(V, E) is called __ if its vertex set V; can be partioned into two disjoined sets V₁ & V₂

Walk

an alternating sequence of vertices and edges; in a __, we list adjacent vertices and edges in a succession

Closed walk

walk where the initial vertex and terminal vertex are the same

Trail

a walk where no edges are repeated (you can repeat vertices)

Circuit

a closed walk where no edges are repeated (you can repeat vertices)

Path

a walk where no vertices are repeated

Cycle

a closed walk where no vertices are repeated

Connected Graph

A graph where there exists a path between any two vertices

Walk

2, 2 (No constraints & Open)

Trail

2, 3 (Can’t revisit Edges & Open)

Circuit

3, 3 (Can’t revisit Edges & Closed)

Path

2, 4 (Can’t revisit Vertices & Open)

Cycle

3, 4 (Can’t revisit Vertices & Closed)