Basics of Graph Theory: Graphs and Terminologies

A __________ graph is a simple graph in which the set of vertices can be partitioned into two sets X and Y such that every edge is between a vertex in X and a vertex in Y

Complete ________ Graph Km,n has m vertices in X and n vertices in Y with an edge between every vertex in X and every vertex in Y

The graph resulting from replacing each arc of a digraph with an edge is called the underlying ________

The ________ of a complete graph is called a Tournament

A ________ graph is a graph with at least one edge and at least one arc

Two graphs are ________ if their sets of vertices and edges are identical

A graph with no loops is called a ______

Two or more edges that join the same pair of distinct vertices are called ______

A graph with at least one loop is called a ______

A vertex of a graph that is not an end of any edge is an ______ vertex

A graph that is in one piece, where each vertex can be reached from all other vertices, is called a ______ graph

A graph without any edges is known as a ______ graph

A simple graph with two vertices may have ______ edge or one edge.

Any simple graph with three vertices gives rise to ______ non-isomorphic cases.

Cyclic Graph Cn = (V, E) (where n > 2) is a graph isomorphic to a graph with V = {v1, v2,..., vn} and E = {{v1, v2}, {v2, v3},..., {vn−1, vn}, {vn, v1}}. Triangle is a cyclic graph with ______ vertices.

The trivial graph is the only graph of order ______.

A graph H = (W, F) is a Subgraph of the graph G = (V, E) if W is a subset of V, and F is a subset of E. Cycle in G - If a subgraph of H of the graph G is a ______ graph.

Clique in G - A complete subgraph of G. Supergraph of G - Any graph G′ for which a given graph G is a ______.

The spanning subgraph obtained by deleting the edges of F from G is denoted by G − ______.

If F consists of one edge f, write G − ______.

The graph obtained from G by deleting every vertex in W as well as any edge in E that is adjacent to the vertices in W is denoted by G − ______.

If W consists of a single vertex w, write G − ______.

A subgraph G′ of G is a Vertex-Induced Subgraph if there exists a set W of vertices in G such that ⟨W⟩ = ______.

A subgraph G′ of G is an Edge-Induced Subgraph if there exists a set F of edges in G such that ⟨F⟩ = ______.

A vertex v is an isolated vertex if d(v)=0. A vertex v is an end vertex if d(v) = ______

A graph is k-Regular if the degree of each vertex is ______

A graph is Regular if there exists a nonnegative integer k that it is ______-regular.

Conjecture: Given the graph G with size ε ε is the number of edges in G 2ε is the total degree of the vertices in G. A vertex in a graph is an Odd Vertex if the degree is ______

In a digraph, the sum of the outdegrees of all vertices is equal to the number of arcs, which is also equal to the sum of all indegrees of all vertices. Indegree (d−(v)) of that vertex - the number of arcs adjacent to a vertex Outdegree (d+(v)) of that vertex - the number of arcs adjacent from a vertex. This is known as the ______

The adjacency matrix of a simple graph is a binary matrix (0, 1) matrix in which each diagonal entry is ______