Discrete Math 1019 Final Exam

Discrete Math 1019 with Albi Kazazi. York University, Summer 2026. 10.1-11.1

What is a graph?

A graph G = (V, E) consists of V—a nonempty set of vertices, and E—a set of edges. Each edge has one or two vertices associated with it, called its endpoints.

What are V and E for the following graph?

V = {a, b, c, d, e}

E = {{a, b}, {a, c}, {b, c}, {b, d}, {c, d}}

True or False: the edge {a, b} is the same as the edge {b, a}

True. The { implies that it is an undirected graph, meaning the order of the vertices does not matter.

What is a simple graph?

A graph in which each edge connects two different vertices(no loops), and no two edges connect the same pair of vertices(no duplicate edges)

True or False: any edge {a, b} in a simple graph is a two-element subset of V.

True.

ex: {a, b} ⊆ {a, b, c, d, e}

True or False: in a simple graph, edges relate vertices symmetrically

True. If an edge {a, b} exists, then a is related to b through that edge, and b is related to a through that edge. Unless a graph is directed, it is symmetric.

What is a multigraph?

A graph in which multiple edges between the same pair of vertices are allowed. Loops, however, are still not allowed.

What is a pseudograph?

A graph in which multiple edges between the same pair of vertices, as well as loops, are allowed.

What is a directed graph?

A graph with directed edges which can be represented as ordered pairs (u, v) of vertices. An edge (u, v) starts at u and ends at v. Directions of edges are represented with arrows.

What are the two types of directed graphs?

Simple directed graph: a directed graph that does not allow loops or repeated directed edges

Directed multigraph: repeated directed edges are allowed, as well as loops.

True or False: the edges (u, v) and (v, u) are the same

False. The ( implies that the graph is directed, and edges are ordered.

What is the m of (u, v) for the following graph?

The multiplicity m for the edge (u, v) is 2, as there are 2 edges (u, v) in this graph.

True or False: a relation R on a set V is best represented by a directed graph on V

True

When an edge (u, v) exists in a graph G, what can we say u is to v and vice versa? What terms can we give u and v?

u is adjacent to v, and v is adjacent from u.

u is the initial vertex of (u, v), and v is the terminal vertex.

What is a mixed graph?

A graph with both directed and undirected edges. They allow loops and duplicate edges.

Which of the following types of graphs allow duplicate edges? Which allow loops?

Simple graph

Multigraph

Pseudograph

Simple directed graph

Directed multigraph

Mixed graph

Simple graph —→ neither

Multigraph —→ only duplicate edges

Pseudograph —→ both

Simple directed graph —→ neither

Directed multigraph —→ both

Mixed graph —→ both

What type of graph would you use to represent acquaintanceships?

Undirected and simple.

Undirected because acquaintanceship is symmetric (if person a has met person b, then person b has met person a).

Simple because it is assumed that a person has met themself(so no loops necessary), and duplicate edges would not make sense in this scenario(if you have met someone once, you are acquainted… no need for multiple edges)

What type of graph would you use to represent websites, where an edge shows if one website links to another?

Directed, simple graph.

Directed because linking is not symmetric (if website a links to website b, that does not imply that b links to a)

Simple because a website would not link back to itself(so no loops necessary), and duplicate edges would not make sense in this scenario(we don’t care about the number of times website a links to website b)

Let G be a simple graph G = (V, E). Consider the relation R on V where uRv if and only if there is an edge {u, v}.

Is R reflexive? Is R symmetric?

Reflexive: No. A simple graph does not allow loops, so an edge {u, u} will never exist, and thus u will never be related to u through R.

Symmetric: Yes. If uRv, then there exists an edge {u, v}. The edge {u, v} is the same as the edge {v, u}. If an edge {v, u} exists, then vRu. So, whenever uRv, vRu.

What does it mean for two vertices u and v to be adjacent? What is a synonym for adjacent?

Vertices u and v are adjacent if an edge {u, v} exists. In other words, if u and v share an edge, they are adjacent.

Neighbors is a synonym for adjacent.

What does it mean for an edge to be incident on a vertex?

An edge is incident on a vertex v if it touches v. In other words, if v is an endpoint of the edge, then that edge is incident on v.

True or False: the edge e is incident on u in the following image

True. u is an endpoint of the edge e.

True or False: the edge e is incident on u in the following image

False. u is not an endpoint of the edge e.

Which vertices are adjacent in the following image? Which are not?

v and u are adjacent, v and w are adjacent.

u and w are not adjacent.

What is the neighborhood of a vertex v? How can it be denoted?

The neighborhood of a vertex v is all of the vertices that are adjacent to v(all of the vertices sharing an edge with v)

It can be denoted by N(v) = {u ∈ V: u is adjacent to v}

What is the neighborhood of a set A⊆V? How can it be denoted?

The neighborhood of a set A⊆V is the union of the neighborhoods of each vertex in A. In other words, all of the vertices that share an edge with a vertex in A.

It can be denoted by N(A) = ⋃ᵥ∈ᴀ N(v) —→ neighborhood of A = the union of N(v) for each v in A.

What is the neighborhood of vertex v in the following image?

N(v) = {a, b, c}

What is the neighborhood of A in the following image if A = {a, b, c}?

N(A) = N(a) ⋃ N(b) ⋃ N(c) = {v} ⋃ {v} ⋃ {v, d} = {v, d}

What is the degree of a vertex? How is it denoted?

The degree of a vertex v is the number of edges incident with v(the number of edges touching v). Loops are counted twice.

The degree of a vertex v is denoted as deg(v)

What do we call a vertex of degree 1? What do we call a vertex of degree 0?

Degree 1: leaf or pendant

Degree 0: isolated

What is the degree of each vertex in the following graph? Which vertices are pendant/leaves? Which vertices are isolated?

deg(a) = 2

deg(b) = 3

deg(c) = 3

deg(d) = 1 —→ pendant/leaf

deg(e) = 4

deg(f) = 1 —→ pendant/leaf

deg(g) = 0 —→ isolated

What is the degree of the vertex c in the following graph?

5 (loops count twice)

What is the Handshaking Lemma?

The Handshaking Lemma is the statement that, in an undirected graph with m edges, the sum of the degrees of each of the vertices is equal to 2m.

True or False: the Handshaking Lemma does not work for loops or multiple edges

False. The Handshaking Lemma works even if multiple edges or loops are present.

If a graph has 10 vertices, each of degree 6, how many edges does that graph have?

The sum of the degrees would be 60, as 10 vertices x 6 degrees is 60.

Because of the Handshaking Lemma, we know that the sum of the degrees is equal to two times the number of edges. So, 60 = 2m.

If 60 = 2m, we can divide both sides by 2 and get m = 30.

What is true about the number of vertices of odd degree in an undirected graph?

In an undirected graph, there is always an even number of vertices of odd degree.

Prove that, in an undirected graph, there is always an even number of vertices of odd degree

We can prove this by splitting the vertices into two groups: the vertices of even degree: Vₑ, and the vertices of odd degree Vₒ.

By the Handshaking lemma, the sum of the degrees of Vₑ + the sum of degrees of Vₒ = 2m.

2m is obviously an even number(2 times any integer is even), and the sum of degrees of Vₑ is obviously even(even + even = even). This means that the sum of degrees of Vₒ must also be even, because it is impossible for an even number + an odd number to equal an even number.

If the sum of degrees of Vₒ is even, but the degrees themselves are odd, that must mean that the number of vertices in Vₒ is even(as an odd number of odd vertices would lead to an odd number).

At a party with 7 people, is it possible that every person shakes hands with exactly 3 others?

No. This would create a graph with 7 vertices of odd degree, which is impossible.

What are the two degrees of a vertex in a directed graph? How is each denoted?

In a directed graph, each vertex has two degrees:

The in-degree (denoted deg⁻(v)), which is the number of edges ending at v.

The out-degree (denoted deg⁺(v)), which is the number of edges starting at v.

What are the in and out degrees of each vertex in the following graph?

deg⁻(a) = 0 deg⁺(a) = 2

deg⁻(b) = 2 deg⁺(b) = 2

deg⁻(c) = 2 deg⁺(c) = 0

What is true about the number of edges in a directed graph?

It is equal to the sum of the in-degrees of each vertex, as well as the sum of the out-degrees of each vertex.

What is the family Kₙ?

A graph Kₙ is a complete graph. It is a simple graph of n vertices, with an edge existing between every pair of vertices.

How many edges are in the graph Kₙ?

Each vertex in Kₙ has degree n - 1 (connected to every other vertex but itself). That means we have n vertices of degree n - 1.

So, by the Handshaking Lemma, n(n - 1) = 2m. Equivalently,

m = (n(n-1))/2

How many edges are in the graph K₆?

6 edges of degree 5 —→ m = (6(5))/2 = 15

What is the family Cₙ?

A graph Cₙ is a cycle with n vertices. A graph Cₙ can not exist if n is less than 3. It is a path where the first vertex connects to the last.

How many edges are in the graph Cₙ?

A graph Cₙ has n edges of degree 2.

So, by the Handshaking Lemma, 2n = 2m. Equivalently,

m = n

How many edges are in the graph C₆?

6 vertices of degree 2 —→ m = (6×2)/2 = 6

What is the family Wₙ?

The wheel Wₙ is obtained from Cₙ by adding one vertex(the hub) adjacent to all n cycle vertices. This means that Wₙ has n + 1 vertices.

How many edges does the graph Wₙ have?

The graph Wₙ has n vertices of degree 3 (2 from the cycle, and one connected to the hub), and one vertex of degree n.

This means that the sum of degrees of Wₙ is (n*3) + n, or 4n.

So, by the Handshaking Lemma, 4n = 2m. Equivalently,

m = 2n

How many edges are in the graph W₆?

6 vertices of degree 3 + 1 vertex of degree 6 —→ m = (4×6)/2 = 12

What is the family Qₙ?

The hypercube Qₙ is a graph in which each vertex represents a bit string of length n. Two vertices are adjacent if and only if they differ in exactly one bit.

Construct the graph Q₂

How many edges are in the graph Qₙ?

The number of vertices in n is equal to 2ⁿ (there are 2ⁿ bit strings of length n), and every vertex has degree n(for a bit string of length n, there are n different bits to disagree on).

This means that the sum of degrees of Qₙ is 2ⁿ*n.

So, by the Handshaking Lemma, 2m = 2ⁿ*n. Equivalently,

m = (2ⁿ*n)/2 = n*2ⁿ⁻¹

How many edges are in the graph Q₃?

2³ = 8 vertices of degree 3 —→ m = (8×3)/2 = 12

How can Qₙ₊₁ be created from Qₙ?

Create two copies of Qₙ, and put an 0 at the end of each string in one copy, and a 1 at the end of each string in the other. Then, add edges that connect two vertices between the two that only differ in one bit.

What is a bipartite graph?

A graph G is bipartite if V can be split into two groups: V₁, and V₂, where no vertices of V₁ exist in V₂ and vice versa(V₁⋃V₂ = V and V₁⋂V₂ = ∅)

AND every edge joins a vertex of V₁ to a vertex of V₂(no edges join V₁ with V₁, or V₂ with V₂).

What is an easy way we can determine whether or not a graph is bipartite?

A graph is bipartite if and only if its vertices can be coloured with two colours, such that no edge joins two vertices of the same colour.

Which of the following graphs are bipartite?

B and D (A and C contain triangles, meaning they need at least 3 colours).

What is the family Kₘₙ?

A graph Kₘₙ is a complete bipartite graph with one set of vertices V₁ of size m, and a second set of vertices V₂ of size n. Every vertex of V₁ is connected to every vertex of V₂, and vice versa. Tr

No edges connect vertices of V₁ with V₁, or V₂ with V₂.

How many edges are in the graph Kₘₙ?

There are m edges of degree n, and n edges of degree m.

This means that the sum of degrees of Kₘₙ is 2mn.

By the Handshaking Lemma, 2m = 2mn. Equivalently,

m = mn

How many edges are in the graph K₂₃?

2 vertices of degree 3 + 3 vertices of degree 2 —→ m = (2(2×3))/2 = 6

What is a matching? What is a complete matching?

A matching M in a graph is a set of edges {u, v} wherein no two edges share a vertex (ex: {{u, v}, {w, z}})

A complete matching from V₁, to V₂ is a matching in which every vertex of V₁ is matched. These occur in bipartite graphs.

Is the following set a matching? {{a, b}, {c, d}, {e, b}}

No. b appears more than once

How can we figure out if a complete matching exists from sets V₁, to V₂?

In a bipartite graph, every subset S of V₁ must have a number of vertices less than or equal to the number of vertices in the neighborhood of S (in order for a complete matching to exist).

|N(S)| ≥ |S| for every subset S⊆V₁

What is a Subgraph? What is a proper subgraph?

A subgraph of a graph G = (V, E) is a graph H = (W, F) with a set of vertices which is a subset of V, and a set of edges that is a subset of E. (So, W⊆V and F⊆E)

A proper subgraph is a subgraph where G ≠ H

How can you denote a subgraph of G where an edge e has been removed?

G - e

Given a graph G = (V, E), what will the vertex and edge sets look like if you remove an edge e? What about if you remove a set of edges E’?

G - e = (V, E - {e}) —→ the set of vertices stays the same, and the edge e is subtracted from the set E.

G - E’ = (V, E = E’) —→ the set of vertices stays the same, and the set of edges E’ is subtracted from the set E.

How can you denote a subgraph of G where an edge e has been added?

G + e

Given a graph G = (V, E), what will the vertex and edge sets look like if you add an edge e?

G + e = (V, E⋃{e}) —→ the set of vertices stays the same, and the edge e is added to the set of edges.

Given the following graph G, what would G - {v1, v2} look like? Is this a subgraph of G?

This is a subgraph of G

Given the following graph G, what would the graph G + {v1, v3} look like? Is this a subgraph of G?

This is not a subgraph of G

Given a graph G = (V, E), what will the vertex and edge sets look like if you remove a vertex v? What about if you remove a set of vertices V’?

G - v = (V - {v}, E’) —→ the set of vertices minus v, and E’: the set of edges in G that are not incident to v(all of the edges from E that do not touch v)

G - V’ = (V - V’, E’) —→ the set of vertices minus the vertices in V’, and the set of edges in G that do not touch any vertices in V’.

For the following graph, if W = {v1, v2, v3}, what is G[W]?

A subgraph of G that keeps only the vertices in W, and the edges in G that have both endpoints in W.

What is the union of two graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂)?

G₁⋃G₂ = (V₁⋃V₂, E₁⋃E₂) —→ the set of vertices+edges is the union of each graph’s set of vertices+edges. If any edges are shared between graphs, they appear only once in the new graph.

What does the union of G₁ and G₂ look like?

Since v2 and v3 are shared by both graphs, as well as their connecting edge {v2, v3}, they all appear only once in the union.

What does G₁⋃G₂ look like if V₁ and V₂ are the same?

The vertex set is the same, and we take the union of the edge sets

What does G₁⋃G₂ look like if V₁ and V₂ have no vertices in common?

The new graph will be two connected components

What is an edge contraction?

Contracting an edge {u, v} involves merging u and v into a single vertex w, and connecting w to every neighbor of u and v(with edges).

Given a graph G = (V, E), what will the vertex and edge sets look like if you contract an edge {u, v}?

V’ = (V - {u, v})⋃{w} —→ V without u and v, and an added vertex w

E’ = edges in E which are not connected to u or v, AND new edges connecting w to every neighbor of u and v.

What would this graph look like if we contracted the edge {u, v}?

What would this graph look like if we contracted the edge {v1, v2}?

What would this graph look like if we contracted the edge {b, c}?

contracted by replacing {b, c} with f

What is an adjacency list? When are they useful?

A chart that lists the neighbors of each vertex. They are useful when the graph has few edges(sparse)

Make an adjacency list for the following graph

How are adjacency lists made for directed graphs?

By listing the terminal vertices of each vertex

Make an adjacency list for the following graph

What is an adjacency matrix?

The adjacency matrix of a graph is a grid with a slot for each combination of vertices. A 1 goes in this slot if those two vertices share an edge, and a 0 goes there if not.

Make an adjacency matrix for the following graph

True or False: adjacency matrixes are symmetric for undirected graphs

True. This can be observed in the following adjacency matrix, where the row and column for v1 are the same.

Given the following adjacency matrix, what is the degree of v1?

2. This is determined by adding up the 1s in the column or row of v1.

Given the following adjacency matrix, how many edges are in this graph?

Adding up each column/row gives the degree of each vertex, so adding up all of the 1s in the matrix gives the sum of degrees of each vertex: 10. So, by the Handshaking Lemma, 2m = 10. Equivalently,

m = 5.

What do adjacency matrixes look like in multigraphs?

The number in each slot is the number of edges between the two vertices

What do adjacency matrixes look like in directed graphs?

In directed graphs, adjacency matrixes are no longer symmetric. The row sum of a vertex is the out-degree (deg⁺(v)), and the column sum of a vertex is the in-degree(deg⁻(v)).

Make an adjacency matrix for the following graph

Draw the graph represented by this adjacency matrix

What are incidence matrices?

Charts that order vertices and edges, where their intersections have a 1 if that vertex is an endpoint of that edge, and a 0 if not.

Give an incidence matrix for this graph

What makes two simple graphs G₁ and G₂ isomorphic?

G₁ and G₂ are isomorphic if there is a bijection V₁ → V₂. In other words, there is some function f that can be applied to an edge {u, v} in E₁ so that {f(u), f(v)} is in E₂

Essentially, if we can relabel the vertices in G₁ and preserve the adjacency of G₂, then the graphs are isometric.

Are these graphs isomorphic? If so, give the bijection

u1—>v1

u2—→v2

u3—→v3

u4—→v4

What are the steps in checking isomorphism?

First, check degrees(a degree-3 vertex can only map to a degree-3 vertex)

Then, check adjacencies.