Graph Theory: Edge Types and Graph Definitions

18 Questions

What is a set of vertices and a set of undirected edges each of which is associated with a set of one or two of these vertices?

An undirected graph

What is the degree of a vertex v in an undirected graph?

The number of edges incident with v with loops counted twice

What is a graph with directed edges that may contain multiple directed edges?

A directed multigraph

What is an edge connecting a vertex with itself?

A loop

What is an undirected graph with no multiple edges or loops?

A simple graph

What is the underlying undirected graph of a graph with directed edges?

The graph obtained by ignoring the directions of the edges

What is the out-degree of the vertex v in a graph with directed edges?

The number of edges with v as their initial vertex

What is a graph with vertex set that can be partitioned into subsets V1 and V2 so that each edge connects a vertex in V1 and a vertex in V2?

A bipartite graph

What is a graph with vertex set that has an edge between each pair of vertices?

A complete graph

What is a characteristic of a simple graph?

It has no multiple edges or loops

What is the term for two vertices connected by an edge?

Adjacent

What type of graph has an edge between each pair of vertices?

Complete graph

What is the in-degree of a vertex v in a graph with directed edges?

The number of edges with v as their terminal vertex

What is a characteristic of a multigraph?

It may contain multiple edges

What is a characteristic of a directed edge?

It is associated with an ordered pair of vertices

What is the term for an edge associated with a set {u, v}?

Undirected edge

What type of graph may contain multiple edges and loops?

Pseudograph

What is the out-degree of a vertex v in a graph with directed edges?