Graph Theory

Question 1

Define an edge

Answer 1

Associates one vertex to itself or another.

Question 2

What is a loop?

Answer 2

An edge with only one endpoint/vertex

Connecting a vertex with itself

Question 3

Define parallel edges.

Answer 3

Two edges that have the same vertex/endpoint

Question 4

When are two vertices adjacent?

Answer 4

When they are connected by an edge

Question 5

Answer 5

Question 6

Answer 6

Question 7

What is a directed graph

Answer 7

A graph in which each edge has a direction (like an arrow pointing from one vertex to another)

Question 8

Given a graph G and vertex, v of G

what does deg(v) denote?

Answer 8

The the degree of v. Meaning the number of edges that are incident on v. Loops are counted twice

Question 9

Answer 9

Question 10

What is the total degree of a graph?

Answer 10

The sum of the degrees of all the verticies of the graph

Question 11

Answer 11

Question 12

Given a graph where n=number of edges, d=total degree

What relation does n and d have?

Answer 12

d=2n. Basically, the total degree is just double the number of edges

Question 13

True or false?

The total degree of graph is even

Answer 13

True. The total degree equals 2 times the number of edges where the number of edges is an integer.

Question 14

Answer 14

Question 15

Answer 15

Question 16

Given a graph with an even number of vertices, what degree does each vertex have (odd or even)

Answer 16

Odd. In a graph with an even number of verticies, each vertex will have an odd degree

Question 17

Answer 17

No. Because it has been proved that a graph with even number of verticies, each vertex must have an odd degree. In the question, there are some with even degrees

Question 18

Answer 18

Question 19

What is a simple graph?

Answer 19

A graph with no parallel edges nor loops. In other words, a graph where no two edges share the same set of end-points

Question 20

Answer 20

Question 21

What is a complete graph?

Answer 21

A type of simple graph where each vertex is connected by exactly one edge

Question 22

Answer 22

Question 23

Answer 23

Question 24

What is a complete bipartite graph?

Answer 24

A graph where the vertices can be partitioned into two subsets (split into two subsets) where each vertex in one subset is connected to a vertex in the other subset by an edge

Note that no vertex is connected to a vertex of the same subset

Question 25

# Given a graph with and verticies v and w What is a trail from v to w?

Answer 25

It is a walk from v to w such that no edges are repeated

Question 26

# Given a graph with and verticies v and w What is a path from v to w?

Answer 26

It is a walk from v to w such that no verticies are repeated

Question 27

# Given a graph What is a closed walk

Answer 27

It is a walk where you start and end on the same vertex

Question 28

# Given a graph What is a circuit?

Answer 28

It is a walk where you start and end on the same vertex (closed walk) such that contains at least one edge and does not contain a repeated edge (trail walk)

Question 29

# Given a graph What is a simple circuit?

Answer 29

It is a walk where you start and end on the same vertex (closed walk) such that contains at least one edge and does not contain a repeated edge (trail walk) nor repeated vertex (path walk) (except for start and end vertex)

Question 30

What is the difference between simple circuit and circuit walk?

Answer 30

A simple circuit is just a circuit but with the added condition that no vertex is repeated (except for start and end vertex)

Question 31

In the graph below, determine which of the following are either trails, paths, closed walks, circuits simple circuits or none of the above (just a walk)

Answer 31

Question 32

# Given a graph G and H When is H said to be a subgraph of G

Answer 32

iff every vertex and edge in H is also in G and that every edge in H has the same endpoints as the corresponding edges in G

Question 33

revision

Question 34

What is the formal definition for a connected graph?

Answer 34

∀ vertices v and w in G, ∃ a walk from v to w | All vertices are connected by a walk (not an edge)

Question 35

Answer 35

Question 36

# True or false? Given verticies v and w that are part of a circuit in graph G. If one edge is removed from the circuit, then there still exists a trail from v to w

Answer 36

True.

Question 37

# Given a graph H and a graph G When is H called the connected component of a graph G

Answer 37

iff 1. H is a subgraph of G 2. H is connected

Question 38

Answer 38

Question 39

What is an Euler circuit

Answer 39

A graph that has a circuit such that every vertex is utilised at least once and every edge is utilised exactly once

Question 40

# True or false? If a graph has an euler circuit, then every vertex of the graph has an even degree

Answer 40

True.

Question 41

Answer 41

Question 42

Given a matrix A and B, when are these matrices equal?

Answer 42

iff A and B have the same size and ∀ entries a, b where a is an entry of A and b is an entry of B, a=b

Question 43

Answer 43

Question 44

What is an adjacency matrix of a graph G?

Answer 44

A matrix that shows the number of edges that connect to each vertex

Question 45

When is a matrix symmetric?

Answer 45

Given any entries a_ij and a_ji of matrix A. Matrix A is symmetric iff a_ij = a_ji

Question 46

What is an incidence matrix?

Answer 46

A matrix which basically shows how many times a vertex is incidence with an edge. (vertex=row, edge=column)

Question 47

When is a graph a tree?

Answer 47

iff it is connected and is circuit-free