ECM 1415 Graph Theory

Question 1

Simple Graph

Answer 1

Each edge connects two different vertices and no two edges connect the same pair of vertices.

Question 2

Multigraphs

Answer 2

Have multiple edges connecting the same two vertices.

Question 3

Pseudograph

Answer 3

May include loops, as well as multiple edges connecting the same pair of vertices

Question 4

Directed graph

Answer 4

Each edge is associated with an ordered pair of vertices (u, v)
Such an edge is said to start at u and end at v
u is the initial vertex of this edge and is adjacent to v and v is the terminal (end) vertex of this edge and is adjacent from u

Question 5

Simple Directed Graph

Answer 5

No loops or multiple edges

Question 6

Directed multigraph

Answer 6

Multiple directed edges

Question 7

Mixed Graph

Answer 7

Can have directed and undirected, with multiple edges and loops

Question 8

Neighborhood

Answer 8

The set of all neighbours of a vertex

Question 9

Degree

Answer 9

The number of incident edges a vertex has
- A loop at a vertex contributes 2 to the degree of that vertex

Question 10

Handshaking Theorem

If G = (V, E) is an undirected graph with m edges then,

Answer 10

2m = Total number of degrees of freedom

Each edge contributes 2 to the degree count of all vertices because an edge is incident with exactly 2 (possibly equal) vertices

This means that the sum of the degrees of the vertices is twice the number of edges

Question 11

In-degrees and Out-degrees

Answer 11

In-degree: The number of edges which terminate at v

Out-degree: The number of edges with v as their initial vertex

Question 12

Let G = (V, E) be a graph with directed edges. Then,

Answer 12

|E| = Number of Out-degrees = Number of In-degrees

Because each edge has an initial vertex and a terminal vertex, the sum of the in-degrees and the sum of the out-degrees of all vertices in a graph with directed edges are the same

Both of these sums are the number of edges in the graph

Question 13

Complete Graph on n vertices

Answer 13

Kn. The simple graph that contains exactly one edge between each pair of distinct vertices

No graph Kn is bipartite for n >= 2

Question 14

Cycle Graphs, Cn

Answer 14

The edges loop. Visually, there is a hole in the graph.

The number of vertices must be even for the graph to be bipartite

Question 15

Wheel graphs, Wn

Answer 15

Like Cn, But there is a vertex in the middle, with all other surrounding vertices connecting to it

The number of vertices must be odd for the graph to be bipartite

Question 16

n-Cube Graphs, Qn

Answer 16

A graph with 2^n vertices representing all bit strings of length n, where there is an edge between 2 vertices that differ in exactly one bit position

No Qn can be bipartite

Question 17

What is a path

Answer 17

A sequence of n edges in a graph

Question 18

What is a circuit

Answer 18

A path that begins and ends on the same vertex

Question 19

When is a path/circuit simple?

Answer 19

If it doesn’t contain the same edge more than once

Question 20

What is a graph isomorphism?

Answer 20

If one graph is isomorphic to another (retains the same base structure)

Question 21

How to find a graph isomorphism between two graphs

Answer 21

Follow paths that go through all vertices so that the corresponding vertices in the two graphs have the same degree

Question 22

What is a connected graph?

Answer 22

An undirected graph is called connected if there is a path between every pair of vertices

An undirected graph that is not connected is called disconnected

We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph

Question 23

The strength of connection in directed graphs (strong and weak)

Answer 23

Strongly connected: There is a path from a to b and a path from b to a whenever a and b are vertices in the graph

Weakly connected: There is a path between every two vertices in the underlying undirected graph

Question 24

Connected component

Answer 24

A connected subgraph

Question 25

Euler Circuit

Answer 25

A simple circuit containing every edge of the graph

Question 26

Euler Path

Answer 26

A simple path containing every edge of G

Question 27

Hamiltonian path/circuit

Answer 27

A simple path/circuit that passes through every vertex exactly once

Question 28

Dirac’s Theorem

Answer 28

If G is a simple graph with n >= 3 vertices such that the degree of every vertex in G is >= (n/2), then G has a Hamilton circuit

Question 29

Ore’s Theorem

Answer 29

If G is a simple graph with n >= 3 vertices such that deg(u) + deg(v) >= n for every pair of nonadjacent vertices, then G has a Hamilton circuit

Question 30

Planar Graph

Answer 30

The graph can be drawn without any edges crossing

Question 31

Euler’s Formula

Answer 31

r = e - v + 2

Question 32

Corollaries (Euler’s Formula)

Answer 32

If G is a connected planar simple graph with e edges and v vertices, where v >= 3, then e <= 3v - 6

If a connected planar simple graph has e edges and v vertices with v >= 3 and no circuits of length three, then e <= 2v - 4

Question 33

How to calculate the number of unique hamilton paths/circuits on a complete graph?

Answer 33

(n-1)! / 2

Question 34

Euler’s Theorem

Answer 34

If a graph has more than two vertices of odd degree, then it cannot have an Euler path. If a graph is connected and has exactly two vertices of odd degree, then it has at least one Euler path (usually more). Any such path must start at one of the odd-degree vertices and end at the other one.