Graph Theory - Terminology and Theory

Question 1

graph

Answer 1

A finite set of vertices and edges where each edge connects two vertices.

Question 2

Example of an algebraic representation of a graph

Answer 2

G = (V, E)
V = {u, v, w}
E = {(u, v), (v, w), (u, w)}

Question 3

True/False: In a graph, each edge must connect two vertices.

Answer 3

True

Question 4

True/False: In a graph, there can be an edge connected to only one vertex.

Answer 4

False; In a graph, each edge must be connected to two vertices. (Also, an edge connected to one vertex leaves the other end of the edge disconnected).

Question 5

T/F: Graphs must be composed of only one connected component/piece overall

Answer 5

False; there exists disconnected vertices, which consists of lone vertices - such graphs are composed of more than one piece/component

Question 6

T/F: Graphs may be composed of more than one piece

Answer 6

True; Disconnected graphs are examples of graphs with more than one piece.

Question 7

T/F: Edges may cross over each other

Answer 7

True

Question 8

T/F: Edges cannot cross over each other

Answer 8

False; edges CAN cross over each other

Question 9

T/F: Graphs can be drawn ONLY in one way

Answer 9

False

Question 10

T/F: Graphs can be drawn in more than one/many ways

Answer 10

True

Question 11

Adjacency

Answer 11

Two vertices u and v are adjacent to each other if and only if there exists an edge (u, v) touching u on one end and v on the other.

Question 12

Incidence

Answer 12

“An edge (u, v) is incident to two vertices u and v” means there is an edge (u, v) that touches u on one end and v on the other end.

Question 13

Self-loop

Answer 13

A curved edge that touches ONLY one vertex on both of its ends

Question 14

Multi-graph

Answer 14

A graph that consists of self-loops and in some pairs of vertices, the vertices are adjacent to each other through multiple edges

Question 15

Simple graph

Answer 15

A graph where there are NO self-loops and in every pair of vertices, the vertices are adjacent to each other through ONLY ONE edge.

Question 16

Degree of a vertex

Answer 16

Number of edges incident on a vertex

Question 17

Degree of a vertex only having a self-loop?

Answer 17

2

Question 18

Degree of a lone/disconnected vertex?

Answer 18

0

Question 19

Path

Answer 19

A contiguous sequence of vertices where in each pair of vertices, the vertices are connected to each other through ONLY one edge.

Question 20

Simple path

Answer 20

A path in which all vertices are distinct; no repetition of any vertex

Question 21

Length of path

Answer 21

No. of edges on a path; it is equal to no. of vertices - 1

Question 22

subpath

Answer 22

A contiguous sub-sequence of vertices; Example: a subpath of a path from u to w consisting of vertices u, v, and w, is <u, v> and <v, w>

Question 23

cycle/circuit

Answer 23

A path that begins and ends at the same vertex and all the edges are distinct

Question 24

simple cycle

Answer 24

A cycle where except for the starting and ending vertex, all vertices are distinct/unique

Question 25

acyclic

Answer 25

A graph with no simple cycles is acyclic

Question 26

connected

Answer 26

A graph is connected if every vertex is reachable to and/or from all other vertices

Question 27

reachable means?

Answer 27

A path exists

Question 28

connected components

Answer 28

The set of vertices in a graph that are reachable to and from each other.

Question 29

T/F: A lone vertex counts as a separate component.

Answer 29

True

Question 30

Eulerian Cycle

Answer 30

A cycle/circuit which traverses EVERY edge of the graph EXACTLY ONCE.

Question 31

Eulerian Path

Answer 31

A path which traverses EVERY edge of the graph EXACTLY ONCE.

Question 32

What are some examples of problems/situations that would use a graph and require a Eulerian Path/Cycle?

Answer 32

Mail delivery, garbage collection, bioinformatics/DNA sequencing, circuit design, routing problems, communications networks, mapping genomes

Question 33

Requirements for the existence of a Eulerian Cycle?

Answer 33

The graph is FULLY CONNECTED & the degrees of ALL vertices are EVEN.

Question 34

Requirements for the existence of a Eulerian Path?

Answer 34

The graph is FULLY CONNECTED & the degrees of EXACTLY TWO vertices is ODD.

Question 35

Euler’s 3rd Theorem

Answer 35

For a graph to exist, there must be an EVEN number of vertices with ODD degrees AND the total sum of degrees must equal to TWICE the total number of edges.

Question 36

Purpose of Euler’s 3rd Theorem?

Answer 36

Proves the existence and possibility of a graph

Question 37

Hamiltonian Cycle

Answer 37

A simple cycle that traverses EACH vertex of the graph ONLY ONCE.

Question 38

Complete Graph

Answer 38

A graph in which every pair of vertices is adjacent.

Question 39

Notation of a complete graph

Answer 39

K_n, where n is the total number of vertices in the graph.

Question 40

Can a complete graph have an Eulerian Cycle? If yes, on what condition

Answer 40

Yes - given the total no. of vertices is ODD; in K_odd number, each vertex is connected to all other vertices, which makes up odd - 1, i.e. even

Question 41

Can a complete graph have a Eulerian Path? If yes, on what conditon, if any?

Answer 41

K_2 is the only complete graph to have a Eulerian Path - for any n > 2, K_n does NOT have a Eulerian Path as either there are more than 2 odd-degree vertices (if n is EVEN) or there are NO odd-degree vertices (if n is ODD)

Question 42

Bipartite graph

Answer 42

A graph where the vertices are partitioned into two sets and ALL the edges in the graph connect vertices from both sets BUT NOT WITHIN the sets.