MATH 350 - DISCRETE MATHEMATICS Graph Theory Question Bank Set 5

MATH 350 - DISCRETE

MATHEMATICS - Graph Theory

Question Bank - Set 5

Liberty University

Question 1

Question

Let Gbe a simple graph with 9 vertices and 17 edges. If the graph Gis connected

and has exactly 2 vertices of degree 1, how many vertices of degree 2 does G

have?

Solution

Step 1: Use the Handshaking Lemma to find the sum of the degrees of all

vertices in G. According to the Handshaking Lemma, the sum of the degrees

of all vertices in a graph is equal to twice the number of edges. Let nbe the

number of vertices in the graph and ebe the number of edges. The sum of the

degrees of all vertices is 2e.

Given that n= 9 vertices and e= 17 edges, the sum of the degrees of all

vertices in Gis 2 ×17 = 34.

Step 2: Use the fact that there are exactly 2 vertices of degree 1 in G. Since

there are 2 vertices in Gwith degree 1, their degree contributes 2 to the sum

of degrees. This means that the sum of the degrees of the remaining vertices is

34 −2 = 32.

Step 3: Calculate the sum of degrees of vertices in Gexcluding the 2 vertices

of degree 1. Let xbe the number of vertices of degree 2 in G. The sum of the

degrees of these vertices is 2x.

From Step 2, we know that the sum of degrees of all vertices except the 2

vertices of degree 1 is 32. So, we have the equation: 2 + 2x= 32

Step 4: Solve for the number of vertices of degree 2 in G. Subtracting 2 from

both sides of the equation gives: 2x= 30

Dividing by 2 on both sides yields: x= 15

Therefore, the graph Ghas 15 vertices of degree 2.

Question 2

Question

Let Gbe a connected graph with nvertices and medges, where n > 2. Prove

that if every vertex in Ghas degree at least n

2, then Gcontains a cycle of length

at most 3.

Solution

Suppose Gis a connected graph with nvertices where every vertex has degree

at least n

Step 1: Consider the vertex with the highest degree. Let vbe a vertex in

Gwith the highest degree. Since every vertex has degree at least n

2, the degree

of vertex vmust be at least n

2.

Step 2: Neighborhood of vertex vSince Gis connected, vertex vmust be

adjacent to at least one other vertex, say u. The degrees of both vand uare at

least n

2, which means there are at least n

2edges incident to each of vand u.

Step 3: Connection between neighbors of vSince uis adjacent to v, the

neighbors of ucannot be the neighbors of v(otherwise, we would have a cycle

of length 3 or less). Therefore, there must be at least n

2vertices in the

neighborhood of uthat are not in the neighborhood of v.

Step 4: Counting vertices The total number of distinct vertices in the

neighborhood of vand uis at least n

2+n

2−1 = n−1. Since Ghas nvertices,

there must be at least one vertex in common between the neighborhoods of v

and u.

Step 5: Forming a cycle Thus, we have found a vertex that is common to the

neighborhoods of vand u, which forms a cycle of length at most 3. Therefore,

if every vertex in Ghas degree at least n

2, then Gcontains a cycle of length at

most 3.

Question 3

Question

Let Gbe a simple, connected graph with 10 vertices such that each vertex has

degree at least 5. Prove that Gcontains a cycle of length at least 4.

Solution

Let’s prove this by contradiction.

Suppose Gis a simple, connected graph with 10 vertices where each vertex

has degree at least 5, but Gdoes not contain a cycle of length at least 4.

Step 1: Determine the minimum number of edges in G. Since Gis a

simple, connected graph with 10 vertices, the minimum number of edges in G

is 10(10−1)

2= 45.

Step 2: Calculate the sum of degrees of vertices in G. Since each vertex in

Ghas degree at least 5, the sum of the degrees of the vertices in Gis at least

10 ×5 = 50.

Step 3: Use the Handshaking Lemma. By the Handshaking Lemma, the

sum of the degrees of the vertices in Gis twice the number of edges. Therefore,

the sum of the degrees of the vertices in Gis even.

Step 4: Analyze the possible cycle lengths. If Gdoes not contain a cycle of

length at least 4, then all cycles in Ghave lengths 3. This means that for each

vertex in G, its neighbors must form a triangle.

Step 5: Derive a contradiction. Since each vertex in Ghas degree at least

5 and all cycles have lengths 3, each vertex in Gmust be adjacent to at most 5

other vertices to avoid forming cycles of length 4 or more. This contradicts the

fact that the sum of the degrees of the vertices in Gis at least 50.

Therefore, our assumption that Gdoes not contain a cycle of length at least

4 must be false. Hence, Gcontains a cycle of length at least 4.

Question 4

Question

Let Gbe a connected graph with 10 vertices and 14 edges. If every vertex in G

has degree at least 2, what is the minimum number of connected components

Gcan have?

Solution

To find the minimum number of connected components in G, we need to consider

the minimum number of edges required for a connected graph with 10 vertices.

Since Gis a connected graph with 10 vertices, the minimum number of edges

in Gcan be found by considering a tree with 10 vertices, which has 9 edges.

Step 1: Calculate the minimum number of connected components in G.

Since Ghas 14 edges, and the minimum number of edges required for a connected

graph with 10 vertices is 9, there are 14 −9 = 5 excess edges in G.

Step 2: Determine the minimum number of connected components. Since

each connected component in a graph must have at least one edge, we can

remove edges from the excess edges in Guntil the graph becomes disconnected.

Removing 4 edges will not disconnect the graph because each vertex has degree

at least 2. However, removing 5 edges will create two disconnected components.

Therefore, the minimum number of connected components Gcan have is 2.

Question 5

Question

Let Gbe a connected graph with 10 vertices and 15 edges. Prove that Gcontains

a cycle with length at least 4.

Solution

To prove that the graph Gcontains a cycle with length at least 4, we will use

the concept of spanning trees and degrees of vertices.

Step 1: Calculate the minimum number of edges in a tree with 10 vertices.

Since Gis a connected graph with 10 vertices, it must have a spanning tree. A

tree with nvertices has n−1 edges. Thus, a tree with 10 vertices has 10 −1=9

edges.

Step 2: Calculate the maximum number of edges in a tree with 10 vertices.

Since a tree with nvertices has n−1 edges, the maximum number of edges in

a tree with 10 vertices is 9.

Step 3: Calculate the number of extra edges in Gapart from the spanning

tree. Since Ghas 15 edges and a spanning tree with 10 vertices has 9 edges,

there are 15 −9 = 6 extra edges in G.

Step 4: Show that there exists a cycle in Gwith length at least 4. Consider

the 10 vertices of Gas the 10 vertices of the spanning tree. Since there are 6

extra edges in G, at least two vertices in the spanning tree must have a degree

greater than 1.

If both vertices have degree 2, then there exists a cycle of length 4 in G. If

one of the vertices has degree greater than 2, then there exists a cycle of length

greater than 4 in G.

Therefore, we have shown that Gcontains a cycle with length at least 4.

Question 6

Question

Let Gbe a connected graph with 10 vertices and 12 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

Let’s prove this by contradiction.

Step 1: Assume that all cycles in Ghave length 3 or less.

Step 2: Let e1, e2, . . . , e12 be the 12 edges of G.

Step 3: Since Gis connected, each vertex must have degree at least 1.

Thus, the sum of the degrees of the vertices is at least 2 ·10 = 20.

Step 4: Using the Handshaking Lemma, we know that the sum of the

degrees of the vertices is equal to twice the number of edges. Therefore, 2|E|=

20, where |E|is the number of edges in G. This implies that |E|= 10.

Step 5: Since each cycle contains at least 3 edges, if there are no cycles

of length at least 4, then Gcan contain at most 3·10

2= 15 edges, which is a

contradiction since Ghas 10 vertices and 12 edges.

Step 6: Hence, our initial assumption was wrong. Therefore, Gmust con-

tain a cycle of length at least 4.

Question 7

Question

Let Gbe a connected graph with 12 vertices and 17 edges. Prove that Ghas a

vertex of degree at most 3.

Solution

To show that Ghas a vertex of degree at most 3, we will use the handshake

lemma and proof by contradiction.

Step 1: Use the Handshake Lemma

The Handshake Lemma states that the sum of the degrees of all vertices

in a graph is equal to twice the number of edges. Mathematically, this can be

expressed as Pv∈Vdeg(v)=2|E|, where Vis the set of vertices, deg(v) denotes

the degree of vertex v, and |E|represents the number of edges in the graph.

Given that Gis a connected graph with 12 vertices and 17 edges, we have:

Pv∈Vdeg(v)=2×17 = 34

Step 2: Assume all vertices have degree at least 4

Suppose every vertex in Ghas degree at least 4. Then, the sum of the

degrees of all vertices would be at least 4×12 = 48, which contradicts the result

from the Handshake Lemma that the sum is equal to 34.

Step 3: Conclude the solution

Since every vertex cannot have a degree of at least 4 without violating the

Handshake Lemma, there must exist a vertex in Gwith degree at most 3.

Therefore, Ghas a vertex of degree at most 3.

Question 8

Question

Let Gbe a simple, connected graph with nvertices, where n≥4. Prove that if

every vertex in Ghas degree at least n

2, then Gis Hamiltonian.

Solution

1. Let’s assume that Gis not Hamiltonian. This means that there does not

exist a cycle in Gthat includes all vertices exactly once.

2. By Dirac’s Theorem, a simple graph with nvertices (n≥3) is Hamiltonian

if every vertex has degree n

2or greater.

3. Since every vertex in Ghas degree at least n

2, by Dirac’s Theorem, G

should be Hamiltonian.

4. As we assumed Gis not Hamiltonian, we have arrived at a contradiction.

Thus, our assumption that Gis not Hamiltonian must be false.

5. Therefore, if every vertex in Ghas degree at least n

2, then Gis Hamilto-

nian.

Question 9

Question

Let Gbe a connected graph with 10 vertices and 15 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To prove that the given graph Gcontains a cycle of length at least 4, we will

use the Pigeonhole Principle.

Step 1: Counting Vertices and Edges Since Gis a connected graph

with 10 vertices, we know that it has at least 9 edges (a connected graph with

nvertices has at least n−1 edges). However, the graph Ghas 15 edges, which

means it has more than the minimum required number of edges.

Step 2: Constructing a Subgraph Let Hbe a subgraph of Gobtained

by repeatedly removing an edge from Gwithout disconnecting it until all the

vertices of Gremain connected. Since Gis connected, this process will result in

removing fewer than 6 edges, leaving Gwith at least 9 edges.

Step 3: Applying the Pigeonhole Principle Since Hhas at least 9

edges, by the Pigeonhole Principle, at least one vertex in Hhas degree at least

2. Thus, there exists a vertex vin Hwith degree 2 or more.

Step 4: Finding a Cycle Since vhas degree at least 2, there exist two dis-

tinct edges incident to v. Traversing these edges creates a cycle in Gcontaining

vertex v. Since a cycle must have at least 3 edges, this cycle has length at least

Therefore, we have shown that the connected graph Gwith 10 vertices and

15 edges contains a cycle of length at least 4.

Question 10

Question

Let Gbe a connected graph with 10 vertices and 14 edges. Prove that Gcontains

a cycle.

Solution

Step 1: We begin by computing the minimum number of edges required for a

connected graph with 10 vertices. To form a connected graph with 10 vertices,

we need at least 9 edges (since a connected graph of n vertices requires at least

n-1 edges).

Step 2: Next, we note that our graph Ghas 14 edges, which is more than

the minimum required for connectivity. This implies that Ghas extra edges

beyond those required to ensure connectivity.

Step 3: Consider adding edges to a tree (a connected acyclic graph) of 10

vertices. Each new edge added to a tree creates exactly one cycle.

Step 4: Since our graph Ghas 14 edges and is connected, it must contain

at least one cycle. This is because the extra edges beyond those needed for

connectivity have created cycles in the graph.

Step 5: Therefore, we have shown that the connected graph Gwith 10

vertices and 14 edges contains a cycle.

Question 11

Question

Let Gbe a connected graph with 12 vertices and 22 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will make use of the

fact that the graph is connected and has 12 vertices and 22 edges.

Step 1: Use the Handshaking Lemma to find the average degree of the

vertices. According to the Handshaking Lemma, the sum of the degrees of all

vertices in a graph is equal to twice the number of edges. Therefore, the average

degree of the vertices in Gis 2×22

12 =44

12 = 32

Step 2: Use the Pigeonhole Principle to show the existence of a vertex with

degree at least 4. Since the average degree of the vertices is 32

3, there must be

some vertex in Gwith degree at least 4. If all vertices have degree 3 or less, the

sum of the degrees would be at most 12 ×3 = 36, which is less than the actual

sum of degrees.

Step 3: Traverse the graph to find a cycle of length at least 4 starting from

the vertex with degree at least 4. Starting from the vertex with degree at least

4, we can traverse the graph to find a cycle of length at least 4. Since the graph

is connected, such a cycle must exist.

Therefore, we have shown that the connected graph Gwith 12 vertices and

22 edges contains a cycle of length at least 4.

Question 12

Question

Let Gbe a connected graph with nvertices and medges. Show that if m<n−1,

then Gis not connected.

Solution

To prove this statement, we will use proof by contradiction.

Step 1: Assume that Gis a connected graph with nvertices and medges

such that m<n−1.

Step 2: By the Handshaking Lemma, the sum of the degrees of all vertices

in a graph is equal to twice the number of edges. Since Ghas nvertices and m

edges, the sum of the degrees of all vertices in Gis 2m.

Step 3: Since Gis a connected graph with nvertices, the sum of the degrees

of all vertices must be at least 2(n−1) = 2n−2, as each vertex must have a

degree of at least 1.

Step 4: However, from Step 2, we know that the sum of the degrees of all

vertices in Gis 2m. Since m < n −1, we have 2m < 2(n−1) = 2n−2, which

contradicts Step 3.

Step 5: Therefore, our initial assumption that Gis a connected graph with

m<n−1 edges must be false. This implies that if m<n−1, then Gis not

connected.

Question 13

Question

Let Gbe a connected graph with nvertices and medges. Prove that if Ghas

a Eulerian path, then there exist at most two vertices in Gwith an odd degree.

Solution

Step 1: Let uand vbe the two vertices in Gwith an odd degree.

Step 2: Since Ghas a Eulerian path, every vertex in Gmust have an even

degree except for uand v.

Step 3: Consider the Eulerian path in G. This path starts at one of the

vertices of uor vand ends at the other. In between, it must visit uand v.

Step 4: Since uand vare the only vertices in Gwith an odd degree, the

Eulerian path must enter uand leave u, and must also enter vand leave v.

Step 5: Therefore, uand vare the only two vertices in Gwith an odd degree.

Thus, if Ghas a Eulerian path, there exist at most two vertices in Gwith

an odd degree.

Question 14

Question

Let Gbe a connected graph with 10 vertices and 15 edges. If there are exactly

3 vertices of degree 4 in G, how many vertices have a degree of at least 5?

Solution

Step 1: We know that the sum of the degrees of all vertices in a graph is equal

to twice the number of edges. Therefore, the sum of the degrees of all vertices

in Gis 2 ×15 = 30.

Step 2: Let xbe the number of vertices with degree at least 5. Since there

are 3 vertices with degree 4, the remaining vertices must have degree less than

5. Therefore, the sum of the degrees of the vertices with degree at least 5 is 5x.

Step 3: We can now write an equation based on the information given:

3×4+5x= 30

Step 4: Solve the equation for x:

12 + 5x= 30

5x= 18

x= 3.6

Step 5: Since the number of vertices must be a whole number, we cannot

have 3.6 vertices with degree at least 5. This means that xmust be at least 4.

Step 6: Therefore, there are at least 4 vertices in Gthat have a degree of

at least 5.

Question 15

Question

Let Gbe a simple graph with 10 vertices such that each vertex has degree at

least 5. Prove that Gcontains a cycle of length at most 4.

Solution

To prove that the graph Gcontains a cycle of length at most 4, we will use the

Pigeonhole Principle.

Step 1: Consider the graph Gwith 10 vertices, each with degree at least

5. Let’s consider a vertex vin G. Since the degree of vis at least 5, when we

remove vand its incident edges from the graph, we are left with a subgraph

with at least 4 vertices.

Step 2: Apply the Pigeonhole Principle. Consider the subgraph obtained

by removing a vertex vwith degree at least 5. This subgraph has at least 4

vertices. By the Pigeonhole Principle, since there are at least 4 vertices and

each vertex has degree at least 5, there must be a vertex uin this subgraph

with degree at least 3.

Step 3: Find a cycle in G. Now, consider the two cases: Case 1: If uis

adjacent to v, then we have a cycle of length 3: u−v−u. Case 2: If uis not

adjacent to v, then since uhas degree at least 3, there must be two vertices,

say w1and w2, adjacent to uthat are distinct from v. Thus, we have a cycle of

length 4: u−w1−w2−u.

Therefore, we have shown that the graph Gcontains a cycle of length at

most 4.

Question 16

Question

Let Gbe a simple graph with 10 vertices and 23 edges. Determine the number

of connected components in G.

Solution

Step 1: Recall that a connected component in a graph is a subgraph in which

any two vertices are connected to each other by paths, and it is not possible to

reach any other vertex outside the subgraph by following the edges.

Step 2: The number of edges in a simple graph with nvertices and kcon-

nected components can be determined using the formula e=n−k+c, where

eis the number of edges, nis the number of vertices, and cis the number of

connected components.

Step 3: In this case, we are given that n= 10 and e= 23. Let cbe the

number of connected components.

Step 4: Substituting the values of nand einto the formula, we have 23 =

10 −c+c.

Step 5: Simplifying the equation, we get 23 = 10. This indicates that there

is a mistake in our calculations.

Step 6: We realize that the mistake occurred in formulating the equation

correctly. The correct equation should be 23 = 10 −c+ 1.

Step 7: Solving the corrected equation, we find c= 12.

Step 8: Therefore, the graph Ghas 12 connected components.

Question 17

Question

Given a simple graph Gwith 10 vertices and 20 edges, prove that Gmust contain

a cycle of length at least 4.

Solution

To prove that the graph Gmust contain a cycle of length at least 4, we will use

the Pigeonhole Principle.

Step 1: Calculate the minimum number of edges in a cycle Let C

be a cycle with the fewest edges in G. Since Ghas 10 vertices, the smallest

cycle Ccan have is a triangle (cycle of length 3), which has 3 edges.

Step 2: Consider the remaining edges Since Ghas 20 edges and the

smallest cycle has 3 edges, there are 17 edges left in Gthat are not part of the

smallest cycle C.

Step 3: Applying the Pigeonhole Principle Consider the 10 vertices in

G. Each vertex can be adjacent to at most 9 other vertices since there are no

self-loops or multiple edges in a simple graph.

Divide the 10 vertices into two sets: those that are part of the smallest cycle

Cand those that are not. There are 10 vertices in total, so at least one set

contains 6 vertices by the Pigeonhole Principle.

Step 4: Finding a cycle If 6 vertices are not in the smallest cycle C, then

at least 6 edges connect these vertices. Since there are no self-loops, at least

one of these 6 edges must connect two of the 6 vertices not in the smallest cycle

C, forming a cycle of length at least 4.

Therefore, we have proved that the graph Gmust contain a cycle of length

at least 4.

Question 18

Question

Let Gbe a connected graph with 10 vertices and 14 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To show that Gcontains a cycle of length at least 4, we will use the concept of

degrees of vertices in a graph.

Step 1: Determine the average degree of vertices Let nbe the number

of vertices in G, and mbe the number of edges in G. Since Gis connected, we

know that m≥n−1. The average degree of a vertex in Gis given by 2m

Given that n= 10 and m= 14, the average degree of a vertex in Gis

2×14

10 = 2.8.

Step 2: Since the average degree is 2.8, there must be a vertex

with degree at least 3 If all vertices in Ghad degree 2, then the average

degree would be 2. Thus, there must be at least one vertex with degree greater

than 2.

Step 3: Consider the neighbors of a vertex with degree at least 3

Let vbe a vertex in Gwith degree at least 3. Since vhas at least 3 neighbors,

there must be a pair of neighbors of vthat are adjacent. Otherwise, vwould

have at most degree 2.

Step 4: Forming a cycle Let uand wbe two neighbors of vthat are

adjacent. Now, the vertices u,v, and wtogether with the edge between uand

wform a cycle of length at least 3. Since uand ware adjacent, this cycle is of

length at least 4.

Therefore, we have shown that the graph Gcontains a cycle of length at

least 4.

Question 19

Question

Let Gbe a connected graph with 10 vertices and 18 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

Step 1: Use the Handshaking Lemma to find the average degree of vertices in

G. According to the Handshaking Lemma, the sum of the degrees of all vertices

in a graph is twice the number of edges. Therefore, the average degree of a

vertex in Gis 2 ×18

10 = 3.6. Since the degree of a vertex must be a non-negative

integer, the average degree implies the existence of a vertex with degree at least

Step 2: Consider a vertex vin Gwith degree at least 4. Let vbe a vertex

in Gwith degree at least 4. Since Gis connected and vhas degree at least 4, v

is connected to at least 4 other vertices in G.

Step 3: Explore the neighbors of vertex v. Since vhas at least 4 neighbors,

there are at least 4 edges incident to v. Without loss of generality, let vbe

connected to vertices a, b, c, and d.

Step 4: Examine the possibilities of connections between neighbors of v.

Consider the vertices a, b, c, and dthat are neighbors of v. If any two of these

vertices are connected, then a cycle of length at least 4 is formed. If none of

these vertices are connected, then adding an edge between any two of them (say

aand b) creates a cycle of length 4. Therefore, in either case, Gcontains a cycle

of length at least 4.

Step 5: Conclusion. Thus, we have shown that any connected graph with

10 vertices and 18 edges must contain a cycle of length at least 4.

Question 20

Question

Let Gbe a connected graph with 10 vertices and 15 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will use the fact that a

connected graph with nvertices and medges contains a cycle of length at least

⌈2m−n+2

n⌉.

Step 1: Calculate the lower bound on the length of a cycle Given

that Ghas 10 vertices and 15 edges, we can calculate the lower bound on the

length of a cycle in G:

Minimum cycle length = ⌈2(15) −10 + 2

10 ⌉=⌈30 −10 + 2

10 ⌉=⌈22

10⌉= 3

Step 2: Prove the existence of a cycle of length at least 4 Since the

minimum cycle length is 3, we know that Gcontains a cycle of length at least

3. To prove that Gcontains a cycle of length at least 4, we will assume that

Gcontains only cycles of length 3. Let c1, c2, . . . , ckbe the cycles in G. Since

each cycle has length 3, each cycle contains 3 edges. Thus, the total number of

edges in all cycles is 3k.

Step 3: Calculate the maximum number of edges Since Ghas 15

edges and the edges in Gare used in the cycles, the maximum number of edges

that can be in these cycles is 15. Therefore, 3k≤15.

3k≤15

k≤5

Step 4: Analyze the cycles If Gcontains at most 5 cycles, and each cycle

has length 3, then there must exist at least one vertex common to two cycles.

This common vertex together with the two cycles forms a cycle of length at

least 4, which contradicts our assumption that Gcontains only cycles of length

Step 5: Conclusion Since our assumption leads to a contradiction, we

conclude that Gmust contain a cycle of length at least 4.

Question 21

Question

Let Gbe a simple graph with 8 vertices and 12 edges. Prove that Gcontains a

subgraph that is a cycle of length at least 4.

Solution

Let us prove the statement by contradiction.

Step 1: Assume that Gdoes not contain a subgraph that is a cycle of length

at least 4.

Step 2: Since Ghas 8 vertices and does not contain a cycle of length at

least 4, the maximum length of any cycle in Gis 3. Thus, each vertex in Gcan

be adjacent to at most 2 other vertices.

Step 3: By the handshaking lemma, the sum of the degrees of the vertices

in a graph is equal to twice the number of edges. In our case, this means

Pv∈Vdeg(v)=2|E|= 24, where Vis the set of vertices and Eis the set of

edges.

Step 4: Since each vertex in Gcan have at most degree 2, the sum of degrees

can be at most 8 ·2 = 16. This is a contradiction with Pv∈Vdeg(v) = 24.

Therefore, our assumption was incorrect.

Step 5: Hence, Gmust contain a subgraph that is a cycle of length at least

Therefore, the original statement is true: Gcontains a subgraph that is a

cycle of length at least 4.

Question 22

Question

Given an undirected graph Gwith 7 vertices and 10 edges, what is the minimum

number of edges that must be removed in order to disconnect the graph?

Solution

To disconnect a graph, we need to remove the minimum number of edges such

that the graph becomes disconnected.

Step 1: Calculate the minimum number of edges required to keep the graph

connected.

The graph with 7 vertices will be a connected graph if it is a tree. A tree

with nvertices has n−1 edges. Therefore, a connected graph with 7 vertices

will have at least 6 edges.

Step 2: Find the excess edges in the graph.

Since the given graph has 10 edges and we determined that at least 6 edges

are needed for connectivity, there are 10 −6 = 4 excess edges in the graph.

Step 3: Remove the excess edges.

To disconnect the graph, we need to remove the excess edges. Therefore, we

must remove all 4 excess edges to disconnect the graph.

Therefore, the minimum number of edges that must be removed in order to

disconnect the graph is 4.

Question 23

Question

Let Gbe a connected graph with 10 vertices and 15 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will use contradiction.

Step 1: Assume Ghas no cycle of length at least 4.

Since Gis a connected graph with 10 vertices and 15 edges, it follows that

Ghas at least 9 edges.

Step 2: Calculate the maximum number of edges in a tree with 10 vertices.

A tree with nvertices has n−1 edges. Therefore, a tree with 10 vertices

can have at most 9 edges.

Step 3: Consider the graph Gwith no cycle of length at least 4.

If Ghas no cycle of length at least 4, then Gis a tree.

Step 4: Contradiction: Gcannot have both 15 edges and be a tree.

We have a contradiction as Ghas 15 edges which is more than the maximum

number of edges a tree with 10 vertices can have.

Thus, our assumption that Ghas no cycle of length at least 4 is false and

there must be a cycle of length at least 4 in G.

Question 24

Question

Let Gbe a connected graph with 10 vertices, each of degree at least 6. Prove

that Ghas a cycle of length at most 6.

Solution

Let’s prove this statement using the Pigeonhole Principle and the concept of

cycles in graph theory.

Step 1: Consider a longest path Pin G.

Assume that Phas length at least 7. Since each vertex in Phas degree at

least 6, each vertex can have at most 2 neighbors not already on P(as otherwise,

the path could be extended). This means that the 10th vertex on Phas at least

6 neighbors on P, creating a cycle.

Step 2: Show that the length of the cycle is at most 6.

If the length of the cycle is more than 6, then at least one of the vertices

on the cycle will have degree more than 6 because each vertex has at least 6

neighbors. This is a contradiction, so the cycle must have length at most 6.

Therefore, we have proven that any connected graph Gwith 10 vertices,

each of degree at least 6, must have a cycle of length at most 6.

Question 25

Question

Let Gbe a simple graph with 10 vertices and 18 edges. Prove that Gis not a

tree graph.

Solution

To prove that a graph is not a tree, we need to show that it has at least one

cycle.

Step 1: Find the minimum number of edges in a tree with 10

vertices. A tree with nvertices has n−1 edges. Therefore, a tree with 10

vertices will have 10 −1 = 9 edges.

Step 2: Consider the number of edges in graph G.Graph Ghas 18

edges, which is greater than the minimum number of edges in a tree with 10

vertices (9 edges).

Step 3: Use the fact that a tree with nvertices contains no cy-

cles. Since a tree is a connected acyclic graph, it does not contain any cycles.

Therefore, since graph Ghas more edges than a tree with the same number of

vertices, it must contain at least one cycle.

Step 4: Conclude that graph Gis not a tree. Since graph Gcontains

at least one cycle, it cannot be a tree. Therefore, Gis not a tree graph.

Question 26

Question

Let Gbe a simple graph with 14 vertices and 27 edges. Determine the maximum

number of vertices in Gthat have degree 7.

Solution

Step 1: Let nbe the number of vertices in Gwith degree 7. Then we have the

equation 7n= 2 ×27 because the sum of the degrees of all vertices in a graph

is twice the number of edges (handshake lemma).

Step 2: Solving for n, we have 7n= 54. Thus, n=54

7≈7.71.

Step 3: Since the number of vertices must be a whole number, the maximum

number of vertices in Gthat have degree 7 is 7 .

Question 27

Question

Let Gbe a connected graph with 12 vertices. Suppose that every vertex in G

has degree at least 6. Prove that Gis Hamiltonian.

Solution

To prove that Gis Hamiltonian, we will show that Gcontains a cycle that visits

every vertex exactly once.

Step 1: Establishing minimum and maximum degree of GSince every vertex

in Ghas degree at least 6, the total number of edges in Gcan be calculated

using the Handshaking Lemma:

2|E|=X

v∈V

deg(v)≥6|V|

where Eis the set of edges in G,|E|is the number of edges in G,Vis the set

of vertices in G, and deg(v) is the degree of vertex v.

Thus, we have |E| ≥ 3|V|.

Step 2: Injective Homomorphism Since Gis connected with 12 vertices, its

average degree is

2|E|

|V|≥2(3|V|)

|V|= 6

This means that there exists an injective homomorphism ffrom Gto K12

(a complete graph on 12 vertices) such that each vertex is mapped to a distinct

vertex in K12 and each edge in Gis mapped to an edge in K12.

Step 3: Longest Path Analysis If there exists a path of length 11 in K12, it

must contain all 12 vertices, making the path a Hamiltonian cycle. Otherwise,

we consider the longest path in G, say with kedges, where k≤11.

Since the path in Gcorresponds to a path in K12 of the same length, we can

add an edge to create a cycle of k+ 1 edges. This cycle will visit every vertex

exactly once, making GHamiltonian.

Therefore, we have shown that a connected graph Gwith 12 vertices and

minimum degree 6 is Hamiltonian.

Question 28

Question

Let Gbe a connected graph with nvertices and medges, where n≥3. Prove

that if every vertex of Ghas degree at least n

2, then Gis Hamiltonian.

Solution

Step 1: Let’s assume Gis not Hamiltonian, and let ube a non-adjacent pair of

vertices in G. Then G+uv is Hamiltonian for any vertex vnot adjacent to u.

Step 2: Since Gis not Hamiltonian, there exists a non-empty strict subset

Sof vertices such that G−Sconsists of two or more components. Let Cbe a

component of G−Swith the minimum number of vertices.

Step 3: Let abe a vertex in C, and let bbe a vertex in V(G)−C. Since G

is connected, there exists an edge ab.

Step 4: Now, let’s consider the degrees of vertices in C. Since Gis not

Hamiltonian, each vertex in Chas degree at most |C| − 1. Thus, the total

number of edges incident with vertices in Cis at most 1

2|C|(|C| − 1).

Step 5: Similarly, the total number of edges incident with vertices in V(G)−

Cis at most 1

2(n− |C|)(n− |C| − 1).

Step 6: Adding the two previous inequalities, we get that the total number

of edges in Gis at most

2|C|(|C| − 1) + 1

2(n− |C|)(n− |C| − 1) = 1

2n(n−1) −1

2|C|(|C| − n).

Step 7: Since |C|< n, we have

2n(n−1) −1

2|C|(|C| − n)>1

2n(n−1) + 1

2n(n− |C|)−1

2|C|n=1

2n2> m,

which contradicts the assumption that Ghas medges. Therefore, our initial

assumption that Gis not Hamiltonian is false. Thus, Gis Hamiltonian.

Question 29

Question

Let Gbe a connected graph with 10 vertices and 15 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will use a proof by

contradiction.

Step 1: Assume that Gdoes not contain a cycle of length at least 4.

Since Gis connected with 10 vertices, the maximum number of edges in G

is 10

2= 45. Since Ghas 15 edges, there are at least 45 −15 = 30 edges that

are not present in G.

Step 2: Consider the shortest cycle in G.

Let v1, v2, . . . , vkbe the vertices in the shortest cycle in G, where k≥3.

This implies that the cycle v1v2. . . vkv1has length at most k.

Since we assumed that Gdoes not contain a cycle of length at least 4, it

follows that k= 3. Thus, the shortest cycle in Gis a triangle.

Step 3: Counting the edges in the graph.

Since the shortest cycle in Gis a triangle, the edges v1v2,v2v3, and v3v1are

present in G. Now, if there are no additional edges between the vertices v1, v2,

and v3, then the total number of edges in Gwould be 3.

Adding additional edges within the triangle leads to cycles of length at least

4. Thus, we must have at least one additional edge between the vertices v1, v2,

and v3.

Step 4: Constructing a cycle of length at least 4.

Consider the additional edge, say v1v4, where v4is a vertex distinct from

v1, v2, v3. Then the cycle v1v2v3v4v1has length 4, which contradicts our as-

sumption.

Therefore, our assumption that Gdoes not contain a cycle of length at least

4 must be false. Hence, Gcontains a cycle of length at least 4.

Question 30

Question

Let Gbe a connected graph with 8 vertices and 13 edges. Prove that Gis not

a tree.

Solution

Step 1: We know that a tree is a connected graph with no cycles. We will prove

that Gmust have a cycle by showing that if Gis a tree, it must follow the

properties n=m−1 and Gis acyclic.

Step 2: Let nbe the number of vertices in Gand mbe the number of edges

in G. Since Gis a tree, it must satisfy n=m−1.

Step 3: Given that n= 8 and m= 13, we have that 8 = 13 −1, which

contradicts the property for a tree. Therefore, Gcannot be a tree.

Step 4: To further prove that Gis not a tree, we will show that Gcontains

a cycle.

Step 5: By the Handshaking Lemma, the sum of the degrees of the vertices

in a graph is twice the number of edges. Therefore, the sum of the degrees of

the vertices in Gis 2m= 2 ×13 = 26.

Step 6: Since Gis connected and not a tree, it must contain at least one

cycle. If Gcontains only one cycle, the sum of the degrees of the vertices in G

would be at least 2 for each vertex on the cycle, and at least 1 for the remaining

vertices.

Step 7: However, if Gcontains one cycle, the sum of the degrees of the

vertices would exceed 26, which is a contradiction. Therefore, Gmust contain

at least two cycles.

Step 8: Hence, we have shown that if Gis a connected graph with 8 vertices

and 13 edges, then Gis not a tree.

Question 31

Question

Let Gbe a connected graph with 11 vertices and 18 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

Step 1: Assume that Gdoes not contain a cycle of length at least 4.

Step 2: Since Gis connected, it must be a tree.

Step 3: By the Handshaking Lemma, the sum of the degrees of the vertices

in a graph is twice the number of edges. Therefore, in a tree with 11 vertices,

the sum of the degrees of the vertices is 2 ×11 = 22.

Step 4: Since Gis a tree, every vertex except the leaves has degree at least

2. Let d1, d2, . . . , dkbe the degrees of the vertices in G(excluding the leaves)

where k≤11. Then, we have d1+d2+. . . +dk≥2k.

Step 5: Since Ghas 11 vertices and no cycles of length at least 4, all vertices

except the leaves have degree exactly 2. Thus, 2 ×(11 −k) + 2k= 22, which

simplifies to 22 −2k= 22 ⇒k= 0.

Step 6: This implies that Gconsists of only vertices of degree 1 and 2,

making Ga path graph. However, a path with 11 vertices only has one possible

cycle of length 3, contradicting our assumption that Gdoes not contain a cycle

of length at least 4.

Step 7: Therefore, our initial assumption was incorrect. Hence, Gmust

contain a cycle of length at least 4.

Question 32

Question

Let Gbe a connected graph with nvertices and medges. Prove that if m<n−1,

then Gis not connected.

Solution

To prove that if m < n −1, then Gis not connected, we will use a proof by

contradiction.

Step 1: Assume that Gis connected despite having m<n−1 edges.

Step 2: By the Handshaking Lemma, we know that the sum of the degrees

of all vertices in a graph is equal to twice the number of edges. In a connected

graph with nvertices and medges, the sum of the degrees of all vertices is at

least 2(n−1), as each vertex must have at least 1 edge incident to it. Therefore,

Pv∈Vdeg(v)≥2(n−1) where Vis the set of vertices.

Step 3: Since Gis connected, we know that the number of edges is at least

n−1. However, we have been given that m<n−1. Therefore, Pv∈Vdeg(v)≥

2(n−1) >2mwhich implies that there exists a vertex vsuch that deg(v)>2.

Step 4: Since Gis connected, there must be a path between any two vertices

in the graph. If we remove the edge incident to the vertex vwith degree greater

than 2, we disconnect the graph into two components. This contradicts our

assumption that Gis connected.

Step 5: Therefore, our initial assumption was incorrect. If m<n−1, then

Gis not connected.

Question 33

Question

Let Gbe a connected graph with 10 vertices and 16 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

We will prove the given statement by contradiction.

Step 1: Assume that Gdoes not contain a cycle of length at least 4. Since

Gis connected and has 10 vertices, the maximum number of edges in Gis

10

2= 45.

Step 2: Let kbe the number of vertices in Gthat have degree at least 3.

Since Gdoes not contain a cycle of length at least 4, each vertex of Gwith

degree at least 3 can have at most two neighbors. Therefore, each of these

vertices can contribute at most 2 to the degree sum, violating the handshaking

lemma if k≥5.

Step 3: The sum of the degrees of the vertices in Gis twice the number of

edges. By the handshaking lemma, the sum of the degrees of the vertices in a

graph is equal to twice the number of edges. In our case, the sum of the degrees

is at most 2n+ 2(k), where nis the number of vertices of degree 2 and kis the

number of vertices of degree at least 3.

Step 4: Combining the information from the previous steps. Since Ghas 10

vertices and 16 edges, the sum of the degrees is at most 2(10) = 20 for a graph

with 10 vertices, all of degree 2. This value increases by at most 2(2) for each

vertex of degree at least 3, giving a total of ≤24. This violates the handshaking

lemma, as the sum of degrees is twice the number of edges, which is 16.

Step 5: Contradiction. Therefore, our assumption that Gdoes not contain

a cycle of length at least 4 must be false, implying that Gcontains a cycle of

length at least 4.

Question 34

Question

Let Gbe a connected graph with nvertices where n≥3. Prove that if every

vertex in Ghas degree at least n

2, then Gis Hamiltonian.

Solution

To prove that the graph Gis Hamiltonian, we will use the Ore’s Theorem which

provides a criterion for Hamiltonicity.

Step 1: State Ore’s Theorem. Ore’s Theorem states: Let Gbe a connected

graph with nvertices where n≥3. If for every pair of non-adjacent vertices u

and vin G, the sum of the degrees of uand vis at least n, i.e., deg(u)+deg(v)≥

n, then Gis Hamiltonian.

Step 2: Prove that Gsatisfies Ore’s Theorem. Given that every vertex in

Ghas degree at least n

2, we need to show that the sum of the degrees of any two

non-adjacent vertices in Gis at least n. Let uand vbe any two non-adjacent

vertices in G. Since Gis a connected graph with nvertices, Ghas (n−1)

edges at least. Each edge contributes 1 to the degree of a vertex. Therefore,

deg(u) + deg(v)≥n

2+n

2=n. Hence, Gsatisfies Ore’s Theorem.

Step 3: Conclude that Gis Hamiltonian. By Ore’s Theorem, since G

satisfies the condition that for every pair of non-adjacent vertices uand v,

deg(u) + deg(v)≥n, it follows that Gis Hamiltonian.

Therefore, we have shown that if every vertex in the connected graph Ghas

degree at least n

2, then Gis Hamiltonian.

Question 35

Question

Let Gbe a connected graph with 10 vertices and 14 edges. Prove that Gcontains

a cycle.

Solution

Step 1: Recall that a connected graph with nvertices has at least n−1 edges

in order to guarantee connectivity. Since Ghas 10 vertices and 14 edges, it is a

connected graph.

Question 2

Question

Let Gbe a connected graph with nvertices and medges, where n > 2. Prove

that if every vertex in Ghas degree at least n

2, then Gcontains a cycle of length

at most 3.

Solution

Suppose Gis a connected graph with nvertices where every vertex has degree

at least n

Step 1: Consider the vertex with the highest degree. Let vbe a vertex in

Gwith the highest degree. Since every vertex has degree at least n

2, the degree

of vertex vmust be at least n

2.

Step 2: Neighborhood of vertex vSince Gis connected, vertex vmust be

adjacent to at least one other vertex, say u. The degrees of both vand uare at

least n

2, which means there are at least n

2edges incident to each of vand u.

Step 3: Connection between neighbors of vSince uis adjacent to v, the

neighbors of ucannot be the neighbors of v(otherwise, we would have a cycle

of length 3 or less). Therefore, there must be at least n

2vertices in the

neighborhood of uthat are not in the neighborhood of v.

Step 4: Counting vertices The total number of distinct vertices in the

neighborhood of vand uis at least n

2+n

2−1 = n−1. Since Ghas nvertices,

there must be at least one vertex in common between the neighborhoods of v

and u.

Step 5: Forming a cycle Thus, we have found a vertex that is common to the

neighborhoods of vand u, which forms a cycle of length at most 3. Therefore,

if every vertex in Ghas degree at least n

2, then Gcontains a cycle of length at

most 3.

Question 3

Question

Let Gbe a simple, connected graph with 10 vertices such that each vertex has

degree at least 5. Prove that Gcontains a cycle of length at least 4.

Solution

Let’s prove this by contradiction.

Suppose Gis a simple, connected graph with 10 vertices where each vertex

has degree at least 5, but Gdoes not contain a cycle of length at least 4.

Step 1: Determine the minimum number of edges in G. Since Gis a

simple, connected graph with 10 vertices, the minimum number of edges in G

is 10(10−1)

2= 45.