Graph Theory Concepts and Definitions

This video tutorial covers additional graph theory definitions, starting with a review of basic graph concepts such as vertices and edges. It explains simple graphs, multigraphs, connected graphs, and complete graphs, including the properties and characteristics of each. The tutorial introduces the handshake lemma, which states that the sum of the degrees of all vertices in a graph is twice the number of edges. This lemma is foundational for understanding more complex graph theory concepts.

What is a graph in graph theory?

• A set of numbers

• An ordered pair of vertices and edges

• A mathematical equation

• A collection of lines

Which of the following is true about simple graphs?

• They can have loops

• They can have multiple edges between the same vertices

• No pair of vertices is connected more than once

• They are always directed

What is a multigraph?

• A graph with no edges

• A graph with only one vertex

• A graph with multiple edges between the same vertices

• A graph with no vertices

What defines a connected graph?

• All vertices are isolated

• There is a path between any two vertices

• It has no edges

• It is a multigraph

What is a complete graph?

• A graph where every pair of vertices is connected by exactly one edge

• A graph with multiple loops

• A graph with no edges

• A graph with only one vertex

How is the degree of a vertex defined?

• The number of vertices in the graph

• The number of edges connected to the vertex

• The number of loops in the graph

• The total number of edges in the graph

How many edges does a complete graph with n vertices have?

• n(n-1)/2

• n

• n(n-1)

• n^2

What does the Handshake Lemma state?

• The sum of the degrees of all vertices is zero

• The sum of the degrees of all vertices is half the number of edges

• The sum of the degrees of all vertices is twice the number of edges

• The sum of the degrees of all vertices is equal to the number of edges

Why must the sum of the degrees of all vertices in a graph be even?

• Because edges are always even in number

• Because vertices are always even in number

• Because graphs are always symmetric

• Because each edge contributes to the degree of two vertices

What is a lemma in mathematics?

• A conjecture

• A hypothesis

• A theorem

• A statement used to establish other results