Graph Theory Flashcards

Graph

nonempty set of vertices and edges connecting vertices

Pendent Vertex

Vertex with a degree of 1

Pendent Edge

Edge that connects to a pendent vertex

Isolated Vertex

Vertex with a degree of 0

End Vertices

The two vertices that are connected by an edge

Parallel Edges

Edges with the same end vertices

Loop

Edge that connects a vertex to itself

Simple Graph

Graph with no parallel edges and loops

Empty Graph

Graph with no edges

Null Graph

Graph with no vertices

Trivial Graph

Graph with only one vertex

Adjacent Edges

Two edges that share a common vertex

Degree

The number of edges which has the vertex as an end vertex, loops are counted twice

Handshaking Theorum

2m = Sum of the degrees of the vertices, where m is the number of edges

Complete Graph

A simple graph which contains all possible edges (Kn)

Cycle Graph

of n vertices, n >= 3, is denoted by (Cn), which is a graph with degree 2 for all vertices.

Wheel Graph

obtains when you add a vertex to the Cycle graph (Cn-1) that is connected to every vertex on the cycle

Bipartite Graph

A graph whose vertices can be divided into two disjoint sets (U and V) such that every edge connects a vertex in U to a vertex in V. No edge connects two vertices within the same set.

Complementary Graph

A graph on the same set of vertices as G, where two distinct vertices are connected by an edge if and only if they are not connected in G.

Walk

A sequence of connected vertices and edges where repetition of both is allowed.

Trail

A walk with no repeated edges

Circuit

A closed path

Cycle

A closed walk

Path

A walk with no repeated vertices and edges except for initial and terminal vertices

Cut Vertex

A vertex of a connected graph whose removal increases the number of connected components

Cut Edge

An edge of a connected graph whose removal increases the number of connected components

Euler Walk

A walk that uses every edge exactly once

Euler Circuit

A closed walk that uses every edge exactly once

Hamilton Circuit

A circuit that uses every vertex in the graph exactly once

Hamilton Path

A path that uses every vertex in the graph exactly once