MATH 350 - DISCRETE MATHEMATICS Graph Theory Question Bank Set 1

MATH 350 - DISCRETE

MATHEMATICS - Graph Theory

Question Bank - Set 1

Liberty University

Question 1

Question

Let Gbe a simple connected graph with 12 vertices and 20 edges. Prove that

Gcontains at least one cycle of length 4.

Solution

To prove that Gcontains at least one cycle of length 4, we will use the Pigeonhole

Principle.

Step 1: Find the minimum number of edges needed to guarantee a

cycle of length 4. In a simple graph with nvertices, the maximum number of

edges without forming a triangle is n

2−1. To guarantee a 4-cycle in a graph,

we need at least 4 edges. Therefore, in a graph with nvertices, the minimum

number of edges needed to guarantee at least one 4-cycle is ⌈n

2⌉.

Step 2: Applying the Pigeonhole Principle. Since Ghas 12 vertices

and 20 edges, there are 20

12 =5

3edges per vertex on average. By the Pigeonhole

Principle, there must be at least one vertex with at least 2 edges incident to it.

Step 3: Constructing the cycle. Start at the vertex with at least 2

incident edges. Follow these edges to two other vertices. If these two vertices

are connected by an edge, then we have formed a cycle of length 3. Otherwise,

there must be a fourth vertex adjacent to one of the two vertices. Travel to this

fourth vertex, forming a cycle of length 4.

Therefore, Gmust contain at least one cycle of length 4.

Question 2

Question

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

a cycle of length at most 4.

Solution

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

fact that the average degree of the vertices in Gis at least 3.

Step 1: Calculate the average degree of the vertices. Let vbe the

number of vertices in the graph Gand ebe the number of edges in G. The

average degree ¯

dof the vertices is given by ¯

d=2e

Substitute v= 10 and e= 18 into the formula:

d=2×18

10 = 3.6.

Step 2: At least one vertex has degree 3 or less. If all vertices in

Ghad degree 4 or more, the sum of all degrees would be at least 4 ×10 = 40,

which is impossible as there are only 18 edges in total. Therefore, at least one

vertex must have degree 3 or less.

Step 3: Find a cycle of length at most 4. Since there is a vertex with

degree 3 or less, we can start at that vertex and trace a path through three

more vertices, forming a cycle of length at most 4. Thus, we have shown that

Gcontains a cycle of length at most 4.

Question 3

Question

Let Gbe a connected graph with 12 vertices and 19 edges. What is the maximum

number of edges that can be added to Gwithout disconnecting it?

Solution

To find the maximum number of edges that can be added to Gwithout discon-

necting it, we need to determine the minimum number of edges required for G

to remain connected.

Step 1: Determine the minimum number of edges required for a connected

graph with 12 vertices. For a connected graph with nvertices, we need at least

n−1 edges to ensure connectivity. Therefore, for a connected graph with 12

vertices, we need at least 12 −1 = 11 edges.

Step 2: Determine the maximum number of edges that can be added with-

out disconnecting G. Given that Galready has 19 edges, we can add at most

12 edges (total vertices - 1) without disconnecting the graph.

Therefore, the maximum number of edges that can be added to Gwithout

disconnecting it is 12.

Question 4

Question

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

a cycle of length at least 4.

Solution

Let nbe the number of vertices in graph G.

Step 1: Determine the number of edges in a tree with nvertices. In a tree

with nvertices, there are n−1 edges. This can be proven by induction on the

number of vertices.

Step 2: Calculate the maximum number of edges in a connected graph with

10 vertices. For a connected graph with nvertices, the maximum number of

edges is given by n(n−1)/2. Therefore, for n= 10 vertices, the maximum

number of edges is 10(10 −1)/2 = 45.

Step 3: Determine the minimum number of edges needed for a cycle of

length 4 in a connected graph with 10 vertices. To form a cycle of length 4 in

a connected graph, we need at least 4 edges.

Step 4: Establish a contradiction. If Gdoes not contain a cycle of length

at least 4, then it is a tree. Since Ghas 18 edges, which is greater than the

maximum number of edges in a tree with 10 vertices (17 edges), this leads to a

contradiction.

Step 5: Conclude. Therefore, if Gis a connected graph with 10 vertices

and 18 edges, it must contain a cycle of length at least 4.

Question 5

Question

Let Gbe a connected graph with nvertices where every vertex has degree at

least n

2. Show that Gis a cycle.

Solution

To prove that Gis a cycle, we will first establish some properties of the graph

and then show that it must be a cycle.

Step 1: Show that Ghas exactly one simple cycle.

Since Gis connected with nvertices, it must have a simple cycle by the Cycle

Existence Lemma in Graph Theory. Let Cbe a simple cycle in Gwith the

maximum number of vertices.

Step 2: Show that Cspans all vertices in G.

Assume there exists a vertex uin Gthat is not part of the cycle C. Every vertex

in Cis connected to at least n

2other vertices. Since there are only nvertices in

total, there must be a vertex in Cconnected to u. This creates a cycle longer

than C, contradicting the maximality of C. Hence, every vertex in Gmust be

in C.

Step 3: Show that Gis a cycle.

Since every vertex in Gis in the cycle C, and Cis a simple cycle with all n

vertices of G,Gmust be the cycle C. Therefore, Gis a cycle.

Thus, we have shown that if a connected graph with nvertices has every

vertex with degree at least n

2, then the graph must be a cycle.

Question 6

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 a graph is Hamiltonian, we must show that there exists a Hamil-

tonian cycle in the graph, i.e., a cycle that visits each vertex exactly once.

Step 1: If Gis a complete graph, then Gis Hamiltonian. Let Kndenote

the complete graph with nvertices. It is known that Knis Hamiltonian for

n≥3.

Step 2: Let Gbe a connected graph with nvertices and each vertex has

degree at least n

2. Since Gis not complete, there exists non-adjacent vertices

uand vin G. Let Ube the set of vertices adjacent to uand Vbe the set of

vertices adjacent to v.

Step 3: Since Gis connected, Uand Vare non-empty. If |U|+|V| ≥ n

(i.e., there are enough vertices to form a Hamiltonian cycle using uand v), then

we can construct a Hamiltonian cycle.

Step 4: Suppose |U|+|V|< n. Since every vertex has degree at least n

then |U|+|V| ≥ n−1. Without loss of generality, assume |U| ≤ n

2−1. Then

|V| ≥ n− |U|> n −(n

2−1) = n

2+ 1.

Step 5: Consider a graph Hobtained from Gby removing uand all edges

incident to u. Since |V| ≥ n

2+ 1, Hhas at least n

2+ 1 vertices. Every vertex in

Hhas degree at least n

Step 6: By induction hypothesis, Hcontains a Hamiltonian cycle. Adding

vertex uand the edges between uand the vertices in Vto the Hamiltonian cycle

in Hforms a Hamiltonian cycle in G.

Therefore, if every vertex in a connected graph Gwith nvertices has degree

at least n

2, then Gis Hamiltonian.

Question 7

Question

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

a cycle.

Solution

To prove that a connected graph Gwith 12 vertices and 15 edges contains a

cycle, we will make use of the fact that in a connected graph with more edges

than vertices, there must be at least one cycle.

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

the vertices. The Handshaking Lemma states that in any graph, the sum of the

degrees of all vertices is equal to twice the number of edges. Therefore, for a

graph with 12 vertices and 15 edges, the sum of the degrees is 2 ·15 = 30. Since

the graph is connected, the average degree of the vertices in Gis 30

12 = 2.5.

Step 2: Deduce that there must be at least one vertex with degree at least

3. If all vertices in Ghad degree at most 2, the sum of the degrees would be at

most 2 ·12 = 24, which is less than the actual sum of degrees (30). Therefore,

there must be at least one vertex with degree at least 3.

Step 3: Use the fact that a connected graph with more edges than vertices

contains a cycle. Since Ghas 15 edges and 12 vertices, which includes at least

one vertex with degree at least 3, there must be at least one cycle in G.

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

15 edges contains a cycle.

Question 8

Question

A simple graph Ghas 10 vertices, each with degree 4. Prove that Gcontains a

cycle of length 3.

Solution

Let’s prove this by contradiction.

Step 1: Assume that there is no cycle of length 3 in the graph.

Step 2: Since every vertex in Ghas degree 4, each vertex is adjacent to 4

other vertices in the graph.

Step 3: Consider a vertex vin G. Since there is no cycle of length 3, the 4

neighbors of vmust be pairwise distinct.

Step 4: Therefore, the 4 neighbors of vcannot have any edges between

them (otherwise, a cycle of length 3 would exist).

Step 5: This means that these 4 neighbors of vare all distinct and form an

independent set in G. Since Ghas 10 vertices and each vertex has degree 4, we

have used up all the remaining 6 vertices.

Step 6: Constructing the graph in this way, we see that there is no way to

add edges between the remaining 6 vertices to form a cycle of length 3 without

violating the condition that there is no cycle of length 3.

Step 7: This is a contradiction, as the initial assumption led to an impossi-

bility. Therefore, our assumption that there is no cycle of length 3 in the graph

must be false.

Step 8: Hence, we have proved that a simple graph Gwith 10 vertices, each

with degree 4, must contain a cycle of length 3.

Question 9

Question

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

a cycle of length at most 4.

Solution

To prove that Gcontains a cycle of length at most 4, we will proceed by con-

tradiction:

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

Since Gis connected with 10 vertices, 13 edges, and does not contain a cycle

of length at most 4, the graph must be a tree. By the property of a tree, a tree

with nvertices always has n−1 edges.

Step 2: Count the number of edges in the tree.

Since Gis a tree with 10 vertices, it must have 10 −1 = 9 edges.

Step 3: Contradiction.

We are given that Ghas 13 edges - a contradiction to our assumption that

Gis a tree. Therefore, our assumption that Gdoes not contain a cycle of length

at most 4 is incorrect.

Since our assumption led to a contradiction, we conclude that Gmust contain

a cycle of length at most 4.

Question 10

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. Suppose Gis a connected graph with nvertices and medges,

where m<n−1.

Step 1: Recall the Handshaking Lemma, which states that the sum of the

degrees of all vertices in a graph is equal to twice the number of edges. Since G

is connected, the sum of the degrees of all vertices is at least 2(n−1).

Step 2: Consider the sum of the degrees of all vertices in G. Let d1, d2, ..., dn

be the degrees of the nvertices in G. Then we have:

d1+d2+· · · +dn≥2(n−1)

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

in Gis equal to 2m. So we have:

2m=d1+d2+· · · +dn

Step 4: Combining the inequalities from Steps 1 and 2, we get:

2(n−1) ≤2m

Step 5: Since m<n−1, we have 2(n−1) ≤2m < 2(n−1), which is

a contradiction. Therefore, our initial assumption that Gis connected when

m<n−1 is false.

Step 6: Hence, if m<n−1, then Gis not connected.

Question 11

Question

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

a cycle.

Solution

Step 1: Let’s start by assuming that Gdoes not contain a cycle. Since Gis

connected, it must be a tree.

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. Since Gis a tree

with 10 vertices, the sum of degrees of all vertices is 2(10 −1) = 18.

Step 3: Since Ghas 13 edges, the sum of degrees of all vertices must be at

least 26. Since 18 ¡ 26, this is a contradiction.

Step 4: Therefore, our initial assumption that Gdoes not contain a cycle is

incorrect. Hence, Gmust contain a cycle.

Question 12

Question

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

a cycle of length at most 6.

Solution

To prove that Gcontains a cycle of length at most 6, we will use a proof by

contradiction.

Step 1: Assume that Gdoes not contain any cycle of length at most 6.

Step 2: By the handshake lemma, the sum of the degrees of all vertices in

Gis twice the number of edges. Since Ghas 10 vertices and 15 edges, the sum

of the degrees of all vertices is 2 ×15 = 30.

Step 3: Since Gis connected, there is at least one vertex of degree at least

1. Let’s consider the shortest path between two such vertices.

Step 4: Suppose the shortest path between two vertices of degree at least 1

is of length d, where d > 6. Since Ghas no cycle of length at most 6, this path

must be a simple path.

Step 5: Along the path, each intermediate vertex (except the start and end

vertices) should have degree 2 (since otherwise, we could shortcut the path and

reduce its length).

Step 6: However, if the path has length d > 6, it will have d+ 1 vertices

including the endpoints. This would contribute at least 2(d+ 1) = 2d+ 2 >

2∗6 = 12 to the sum of degrees, which contradicts the fact that the sum of

degrees is 30.

Step 7: Therefore, our initial assumption that Gdoes not contain any cycle

of length at most 6 must be false. Hence, Gcontains a cycle of length at most

Question 13

Question

Let Gbe a connected graph with 12 vertices and 16 edges. If Ghas exactly one

cycle, how many vertices and edges does this cycle have?

Solution

Let vbe the number of vertices in the cycle and ebe the number of edges in the

cycle. Since Ghas 12 vertices and 16 edges, by Euler’s formula for connected

graphs we have v−e+ 1 = 12 −16 + 1 = −3.

Since Ghas exactly one cycle, all other edges must be part of the spanning

tree. Therefore, the total number of edges in the graph is v−1. This gives us

the equation v−1 = 16.

Solving the system of equations v−e+ 1 = −3 and v−1 = 16, we find

v= 17 and e= 16. Thus, the cycle in Ghas 17 vertices and 16 edges.

Question 14

Question

Let Gbe a simple graph with 10 vertices and 20 edges. Prove that Gcontains

a cycle of length at most 4.

Solution

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

Principle.

Step 1: Computing the average degree Since Ghas 10 vertices and 20

edges, the average degree of the vertices in Gis 2 ×20

10 = 4. This means there

must be at least one vertex with degree less than or equal to 4.

Step 2: Constructing a subgraph Let vbe a vertex in Gwith degree

less than or equal to 4. Removing vand its incident edges from G, we obtain a

subgraph G′with 9 vertices and at most 19 edges.

Step 3: Applying the Pigeonhole Principle In the graph G′, the aver-

age degree of the vertices is at most 2 ×19

9≈4.22. By the Pigeonhole Principle,

there must exist a vertex uwith degree at most 4 in G′.

Step 4: Finding a short cycle Since uhas degree at most 4 in G′, there

are at most 4 vertices adjacent to u. If any two of these vertices are adjacent

in G′, then a cycle of length at most 4 is formed. If no such pair exists, then u

must have at least 5 neighbors forming a subgraph K5, which contains a cycle

of length 3.

Therefore, we have shown that Gcontains a cycle of length at most 4.

Question 15

Question

Let Gbe a simple undirected 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 Pigeonhole

Principle.

Step 1: Determine the maximum number of edges in a tree. A tree

with 10 vertices has 9 edges. This is because a tree with nvertices has n−1

edges.

Step 2: Calculate the number of edges exceeding a tree. Since G

has 15 edges, there are 6 edges more than a tree with 10 vertices.

Step 3: Consider the possible connections of the extra edges. Each

extra edge connects two vertices, which either form a cycle or extend an existing

cycle.

Step 4: Use the Pigeonhole Principle. A cycle with 4 or more vertices

must have at least 4 edges. Since there are 6 extra edges, at least one of the

extra edges completes a cycle of length at least 4.

Therefore, Gcontains a cycle of length at least 4.

Question 16

Question

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

a cycle of length at most 4.

Solution

To show that Gcontains a cycle of length at most 4, we will use the Pigeonhole

Principle.

1. Let nbe the number of vertices in G, and mbe the number of edges in

G. In this case, n= 10 and m= 18.

2. By the Handshaking Lemma, the sum of degrees of all vertices in a graph

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

in Gis 2m= 36.

3. Since each vertex in Gis connected to at least one other vertex (as Gis

connected), the average degree of a vertex in Gis 2m

n=36

10 = 3.6. This

means there exists at least one vertex with degree at most 4.

4. Select a vertex vin Gwith degree at most 4. Consider the vertices adjacent

to v- there are at most 4 such vertices. Let these vertices be u1, u2, u3, u4.

5. If any of the vertices uiare connected to v(creating a cycle of length 3),

then we are done. Otherwise, each uimust be connected to at least one

other uj(i=j) to avoid creating a cycle of length 2.

6. By the Pigeonhole Principle, at least two of the vertices uiare adjacent

to the same vertex uj(i=j). This creates a cycle of length at most 4.

Therefore, we have shown that Gcontains a cycle of length at most 4.

Question 17

Question

Let Gbe a simple, 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 Pigeonhole

Principle.

Step 1: Find the minimum number of edges needed for Gto guar-

antee a cycle of length 3. For a graph to guarantee a cycle of length 3, it

must contain 3 vertices connected by edges. The minimum number of edges

needed for this is 3

2= 3.

Step 2: Consider the remaining 7 vertices in G.Since Ghas 10

vertices and 15 edges, there are 7 remaining vertices after the 3 vertices in our

minimum cycle of length 3.

Step 3: Apply the Pigeonhole Principle. Divide the 7 remaining ver-

tices into 3 groups, where each group contains at least 3 vertices. By the Pi-

geonhole Principle, at least one group must contain 4 vertices.

Step 4: Create a cycle of length at least 4. In the group with 4 vertices,

there must be at least 3 edges connecting these vertices. Adding these edges to

the minimum cycle of length 3, we form a cycle of length at least 4.

Therefore, we have shown that any simple, connected graph Gwith 10 ver-

tices and 15 edges contains a cycle of length at least 4.

Question 18

Question

Let Gbe a connected graph with 10 vertices where each vertex has degree at

least 3. Prove that Gcontains a cycle of length at least 4.

Solution

Let’s prove this by contradiction.

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

Step 2: Since Gis connected and does not contain a cycle of length at least

4, each face in the planar representation of Gmust have length 3.

Step 3: By Euler’s formula, v−e+f= 2, where vis the number of vertices,

eis the number of edges, and fis the number of faces. Since Gis connected

and planar, e≤3v−6 and f≤2v−4.

Step 4: On the other hand, the sum of the degrees of the vertices in a graph

is equal to twice the number of edges. Since each vertex in Ghas degree at least

3, the sum of the degrees of the vertices is at least 3v. Therefore, 2e≥3v.

Step 5: Combining the inequalities from Step 3 and Step 4, we have: 3v≤

2e≤6v−12

0≤3v−12

12 ≤3v

4≤v

Step 6: Since Ghas 10 vertices, we have reached a contradiction. Therefore,

our initial assumption that Gdoes not contain a cycle of length at least 4 is

false.

Step 7: Hence, we conclude that Gmust contain a cycle of length at least

Question 19

Question

Let Gbe a simple connected graph with 11 vertices and 17 edges. Prove that

Gcontains a cycle of length at most 5.

Solution

Step 1: We begin by considering the case where Gcontains a vertex of degree at

most 2. If there exists a vertex of degree 1 in G, then removing that vertex would

reduce the number of edges by 1 but keep the graph connected, creating a cycle

of length 1. Similarly, if there exists a vertex of degree 2 in G, then removing

that vertex together with its incident edges would preserve connectivity while

creating a cycle of length 2.

Step 2: Now, assume that all vertices in Ghave degree at least 3. Using 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. Therefore, the sum of the degrees

of all vertices in Gis 2 ×17 = 34.

Step 3: Since Ghas 11 vertices and each vertex has degree at least 3, the

sum of the degrees of all vertices must be at least 11 ×3 = 33. This implies

that the sum of the degrees of all vertices is exactly 34.

Step 4: We observe that it is not possible for all vertices in Gto have degree

exactly 3 because that would imply a total degree of 11 ×3 = 33, which is less

than 34. Hence, there must exist at least one vertex in Gwith degree greater

than 3.

Step 5: Consider a vertex vin Gwith degree at least 4. Since Gis connected

and vhas at least 4 neighbors, there must exist at least two distinct neighbors

of vthat are adjacent to each other. Let these neighbors be uand w, where u

and ware distinct vertices.

Step 6: The existence of edges uv and vw along with the edge vw creates

a cycle of length at most 5 in G(specifically, the cycle formed by the vertices

u, v, w). Therefore, we have shown that Gmust contain a cycle of length at

most 5.

Question 20

Question

Let Gbe a connected graph with 12 vertices and 17 edges. If Ghas exactly two

vertices of degree 3 and all other vertices of degree 4, how many cycles of length

4 does Gcontain?

Solution

Let nbe the number of cycles of length 4 in G.

Step 1: Find the total degree sum of the graph. Since the sum of the

degrees of the vertices in a graph is twice the number of edges, we have:

2|E|=Xdegree of v

2×17 = 12 ×4+2×3

34 = 48 + 6

34 = 54

Step 2: Deduce a contradiction. Since the total degree sum is not equal to

2 times the number of edges, we have a contradiction. Therefore, there are no

cycles of length 4 in the graph G.

Question 21

Question

Let Gbe a simple 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 assume the contrary

and reach a contradiction using the Handshaking Lemma and the Cycle Lemma.

Step 1: Calculate the minimum number of edges a graph with

10 vertices can have. The minimum number of edges in a simple connected

graph with 10 vertices occurs when the graph is a tree. A tree with nvertices

has n−1 edges. Thus, a graph with 10 vertices must have at least 9 edges.

Step 2: Calculate the maximum number of edges a graph with

10 vertices can have. The maximum number of edges in a simple connected

graph with 10 vertices occurs when the graph is a complete graph. A complete

graph with nvertices has n(n−1)

2edges. Thus, a graph with 10 vertices can have

at most 10·9

2= 45 edges.

Step 3: Determine the number of edges in our graph G.Given

that Ghas 15 edges, our graph falls between the minimum of 9 edges and the

maximum of 45 edges for 10 vertices.

Step 4: Derive a contradiction by assuming the absence of a cycle

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

least 4. Then, every cycle in Gmust be a triangle (3 vertices) or a line segment

(2 vertices), as adding any additional vertex would create a cycle of length at

least 4.

Step 5: Use the Cycle Lemma to find the maximum number of

edges in a graph with only 2 or 3 vertices. Applying the Cycle Lemma, a

graph with nvertices and no cycle of length at least 4 can have at most nedges.

Thus, in our case where all cycles are triangles or line segments, the 10-vertex

graph Gwith no cycles of length at least 4 can have at most 10 edges.

Step 6: Derive a contradiction using the number of edges in G

(15) and the maximum allowed edges. Since Ghas 15 edges and under

our assumption, a graph without cycles of length at least 4 can have at most

10 edges, we have reached a contradiction. Hence, our assumption that Gdoes

not contain a cycle of length at least 4 is false.

Therefore, Gmust contain a cycle of length at least 4.

Question 22

Question

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

a cycle of length at least 4.

Solution

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

make use of the fact that Ghas more edges than vertices.

Step 1: Determine the minimum number of edges needed for a

cycle of length 4 In any cycle of length 4, there are 4 vertices and 4 edges.

So, the minimum number of edges needed for a cycle of length 4 is 4.

Step 2: Use the fact that Ghas more edges than vertices Since G

has 12 vertices and 16 edges, and there are more edges than vertices, there must

be at least one vertex of degree at least 2 by the Pigeonhole Principle.

Step 3: Construct a path starting from a vertex of degree at least

2Start at a vertex vof degree at least 2. Move along an edge to a neighboring

vertex uand continue doing so until you revisit a vertex.

Step 4: The path forms a cycle Since the graph is connected, the path

must end at the starting vertex v. This forms a cycle in the graph.

Step 5: Analyze the length of the cycle The cycle obtained in step 4

might have length less than 4. If it’s exactly 4, we are done. If not, the cycle

must contain a repeated vertex which introduces a smaller cycle within it.

Step 6: Conclusion Therefore, we have shown that the graph Gmust

contain a cycle of length at least 4.

Question 23

Question

Given a simple graph Gwith 10 vertices and 20 edges, is it possible for Gto

have 5 vertices of degree 4 and 5 vertices of degree 5? Justify your answer.

Solution

Step 1: Recall the Handshaking Lemma, which 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 written as: X

v∈V

deg(v) = 2|E|

Step 2: Let’s calculate the total sum of the degrees of the vertices based on

the given information. If Ghas 5 vertices of degree 4 and 5 vertices of degree

5, the total sum of degrees is:

5×4+5×5 = 20 + 25 = 45

Step 3: Since Ghas 20 edges, according to the Handshaking Lemma, the

total sum of degrees must be twice the number of edges, which is 40. Since our

calculated total sum is 45, this violates the Handshaking Lemma.

Step 4: Therefore, it is not possible for a simple graph with 10 vertices and

20 edges to have 5 vertices of degree 4 and 5 vertices of degree 5 simultaneously.

Question 24

Question

Let Gbe a connected graph with 10 vertices and 17 edges. Prove that Gmust

contain a cycle of length at most 4.

Solution

To prove that a connected graph Gwith 10 vertices and 17 edges must contain

a cycle of length at most 4, we will use the Pigeonhole Principle.

Step 1: Determining Maximum Number of Edges By the Handshak-

ing Lemma, the sum of the degrees of the vertices in a graph is twice the number

of edges. Since Gis connected and has 10 vertices, the sum of the degrees of

the vertices is at least 2 ×17 = 34.

Step 2: Existence of Short Cycles Consider the longest path in G. Since

Gis connected, this path must have at most 9 edges. Thus, adding 1 more edge

creates a cycle. This cycle must have length less than or equal to 4, as a cycle of

length 5 or greater would create a longer path than the assumed longest path.

Step 3: Conclusion Therefore, we have shown that in a connected graph

Gwith 10 vertices and 17 edges, there must exist a cycle of length at most 4.

Question 25

Question

Let Gbe a connected graph with 15 vertices and 24 edges. If each vertex in

Ghas degree at least 3, what is the minimum number of vertices with degree

exactly 3 in G?

Solution

Let nbe the number of vertices with degree exactly 3 in G. Since each vertex

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

3×15 = 45. Also, the sum of the degrees of all vertices in a graph is equal to

twice the number of edges. Therefore, we have 2 ×24 = 48 as the sum of the

degrees of all vertices in G.

Step 1: Set up an inequality based on the given information. Since the sum

of the degrees of all vertices in Gmust be at least 45, we have the following

inequality:

3n+ 3(15 −n)≥45

Step 2: Solve the inequality to find the minimum value of n. Simplifying

the inequality gives:

3n+ 45 −3n≥45

45 ≥45

Since the inequality is true for all values of n, the minimum number of

vertices with degree exactly 3 in Gis 0 .

Question 26

Question

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

a cycle of length at least 4.

Solution

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

proof by contradiction.

Step 1: Assume Gdoes not contain a cycle of length at least 4. Then, the

maximum cycle length in Gis 3.

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

in G. Since Gis connected, we have n−1≤m≤n(n−1)

2(by the Handshaking

Lemma).

Given that n= 12 and m= 16, we know that 16 ≥11 (from the condition

n−1≤m) and 16 ≤66 (from the condition m≤n(n−1)

2).

Step 3: Next, we observe that if every vertex in Ghas degree 2, then G

consists of disjoint cycles and the maximum cycle length is 3 in this case.

Since the total number of edges in Gis 16 and each edge contributes 2 to

the sum of the degrees of the vertices, we have Pv∈Vdeg(v)=2·16 = 32.

Step 4: Now, suppose Gdoes not contain a cycle of length at least 4. Then,

every vertex in Ghas degree 2.

As all vertices have degree 2, the total number of edges is 1

2Pv∈Vdeg(v) =

2·32 = 16.

Step 5: However, this contradicts the given condition that Ghas 16 edges.

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

least 4 must be false.

Thus, we conclude that the graph Gmust contain a cycle of length at least

Question 27

Question

Let Gbe a simple graph with 9 vertices and 27 edges. Determine whether G

contains a cycle of length 5.

Solution

Step 1: Let’s start by examining the maximum number of edges a graph with 9

vertices can have in order to not contain a cycle of length 5.

Step 2: The maximum number of edges in a graph without a cycle of length

5 is when the graph is a tree. In a tree with nvertices, there are n−1 edges.

Step 3: Therefore, for a graph with 9 vertices to not contain a cycle of length

5, it can have at most 9 −1 = 8 edges.

Step 4: Since we are given that the graph Ghas 27 edges, which is more

than 8, we can conclude that Gmust contain a cycle of length 5.

Step 5: Therefore, the graph Gcontains a cycle of length 5.

Question 28

Question

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

a triangle.

Solution

To prove that the simple graph Gcontains a triangle, we will make use of the

Pigeonhole Principle.

Step 1: Finding the maximum number of edges in a simple graph

with 10 vertices A simple graph with nvertices can have at most n(n−1)

edges. For n= 10, the maximum number of edges is 10·9

2= 45.

Step 2: Applying the Pigeonhole Principle Given that Ghas 18 edges,

we note that this number is less than the maximum of 45 edges that could be

in G. We want to show that there must be a triangle in G.

Step 3: Considering the complement of GLet G′be the complement

of G, which is a simple graph with 10 vertices and 45 −18 = 27 edges.

Step 4: Applying the Pigeonhole Principle to G′In G′with 10 vertices

and 27 edges, there must be a pair of vertices that are connected by an edge.

Otherwise, all pairs of vertices would be disconnected, contradicting the presence

of 27 edges.

Step 5: Relationship between Gand G′In G, if there is no edge between

the pair of vertices in G′, then the vertices form a triangle in G.

Step 6: Conclusion Therefore, since G′contains a pair of vertices con-

nected by an edge, we have found a triangle in the original graph G. Thus, G

contains a triangle.

Question 29

Question

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

a cycle of length at most 4.

Solution

To prove that Gcontains a cycle of length at most 4, we will show that if there

is no cycle of length at most 4, then the graph Gcannot have 15 edges with 10

vertices.

Step 1: Suppose Ghas no cycle of length at most 4. Let us suppose

that Ghas no cycle of length at most 4. Then every cycle in Gmust have length

at least 5.

Step 2: Counting edges in terms of vertices. For a graph Gwith n

vertices and no cycle of length at most 4, each cycle in Gmust have length at

least 5. We know that a cycle of length khas kedges. Therefore, in Gwith

cycles of length at least 5, the average number of edges in each cycle is at least

Step 3: Counting maximum number of edges. The maximum number

of edges in a graph with 10 vertices is 10

2= 45. If Ghas 15 edges, then there

must be at least 3 vertices with degree 4, as each edge contributes 2 to the

degree of a vertex.

Step 4: Applying the Handshaking Lemma. By the Handshaking

Lemma, the sum of the degrees of all vertices in a graph is twice the number

of edges. If Ghas 10 vertices and 15 edges, then the sum of the degrees of the

vertices is 2·15 = 30. Since at least 3 vertices have degree 4 to achieve 15 edges,

there must exist a cycle of length at most 4 in G.

Therefore, we have reached a contradiction, and the assumption that Ghas

no cycle of length at most 4 must be false. Hence, Gmust contain a cycle of

length at most 4.

Question 30

Question

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

vertex in Ghas degree at least n/2, then Gcontains a cycle.

Solution

To prove that Gcontains a cycle, we will use the principle of pigeonhole.

Step 1: Consider the longest path Pin G. Assume Phas endpoints vand

w. Since Gis a connected graph, there exists a path from vto w. Let xbe a

vertex on this path. Note that xcannot be in Psince Pis assumed to be the

longest path in G.

Step 2: Show that xmust have a neighbor in P. Since xis not in P, it

must have a neighbor yin P. Otherwise, Pcould be extended by adding xto

the path.

Step 3: Forming a cycle using Pand the path from xto y. Consider the

path from vto xin P, then from xto y, and finally from yto win P. This

forms a closed walk that is not necessarily a cycle. However, note that xand

yare not the endpoints of the path, so there exist vertices in the path between

xand y. Therefore, this closed walk contains a repeated vertex, which forms a

cycle.

Thus, Gcontains a cycle as desired.

Question 31

Question

Let Gbe a connected graph with 14 vertices and 22 edges. Prove that Gmust

contain a cycle of length at least 4.

Solution

Step 1: Let’s first determine the minimum number of edges required for a graph

with 14 vertices to be connected.

Step 2: By the Handshake Theorem, the total degree of a graph is twice the

number of edges, i.e., Pv∈Vdeg(v) = 2|E|.

Step 3: Since Gis connected, each vertex has degree at least 1. Thus, the

total degree of the graph is at least 14.

Step 4: Now, consider the worst case scenario where all vertices except one

have degree exactly 1.

Step 5: In this scenario, the remaining vertex must have degree at least

14 −13 = 1 in order for the graph to be connected.

Step 6: Therefore, the minimum number of edges required for a connected

graph with 14 vertices is 14 −1 = 13.

Step 7: Since Ghas 22 edges, it contains more than the minimum number

of edges required for connectivity.

Step 8: We know that a tree (a graph with no cycles) on nvertices has n−1

edges.

Step 9: Therefore, there must be at least 22 −(14 −1) = 9 edges in Gthat

are part of cycles.

Step 10: Now, suppose that Gcontains no cycle of length at least 4.

Step 11: Any cycle in Gmust have at least 3 edges. Therefore, those 9 edges

must form at least 3 cycles.

Step 12: However, each vertex can only belong to one cycle. So, in order to

have 3 cycles, Gmust have at least 3*4=12 vertices.

Step 13: This contradicts the fact that Ghas only 14 vertices.

Step 14: Therefore, Gmust contain a cycle of length at least 4.

Question 32

Question

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

cycle of length k, where k≥4, then Ghas at least n−k+ 1 vertices of degree

at least 2.

Solution

To prove this statement, we will use the concept of the Handshaking Lemma,

which states that the sum of degrees of all vertices in a graph is twice the number

of edges.

Step 1: Define the cycle Let Cbe a cycle of length kin Gwith vertices

v1, v2, . . . , vk, where edges (vi, vi+1) are in Cfor 1 ≤i≤k−1 and (vk, v1) is

also in C.

Step 2: Vertices in Chave degree at least 2 Each vertex viin the cycle

Chas degree at least 2 since it is connected to the two adjacent vertices vi−1

and vi+1 in the cycle, and possibly to additional vertices outside the cycle.

Step 3: Vertices not in Cmay have degree 1 Any vertex not in the

cycle Cmay have degree 1 if it is connected only to the vertex viin the cycle.

These vertices are the vertices of degree exactly 1 in G.

Step 4: Counting the minimum number of vertices of degree at

least 2 Since the sum of degrees of all vertices in Gis twice the number of edges,

we have Pv∈Vdeg(v)=2m. Let n′be the number of vertices of degree at least

2, then the sum of degrees of these vertices is at least 2(n′−(n−n′)) = 4n′−2n.

Since each vertex in Chas degree at least 2 and each vertex not in Chas degree

1 or higher, we have Pv∈Vdeg(v)≥2k+ (n−n′)≥4n′−2n(as k≥4). Thus,

2k+ (n−n′)≥4n′−2nand rearranging gives n′≥n−k+ 1.

Therefore, Ghas at least n−k+ 1 vertices of degree at least 2.

Question 33

Question

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

at least one cycle.

Solution

Step 1: Recall that a graph is said to be acyclic if it does not contain any cycles.

So, to prove that Gcontains at least one cycle, we will assume the contrary, i.e.,

we will assume that Gis acyclic and arrive at a contradiction.

Step 2: Since Gis acyclic, it is a tree. By the Tree Theorem, we know that

a tree with nvertices has n−1 edges. Therefore, if Ghas 12 vertices and is

acyclic, it must have 12 −1 = 11 edges, which is a contradiction to the given

information that Ghas 20 edges.

Step 3: Since our assumption that Gis acyclic leads to a contradiction, we

can conclude that Gmust contain at least one cycle. Thus, the statement has

been proved.

Question 34

Question

Let Gbe a connected graph with 12 vertices and 17 edges. 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 reason

by contradiction.

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

Step 2: If Gdoes not contain a cycle of length at most 4, then every cycle

in Gmust have a length of at least 5. Let cbe the number of vertices in the

shortest cycle of G.

Step 3: Since Ghas 12 vertices and 17 edges, by the handshaking lemma,

the sum of the degrees of all vertices in Gis twice the number of edges, which

is 34.

Step 4: The length of the shortest cycle must be at least 5, so the sum of

the degrees of the vertices in this cycle is at least 5c. Since each edge contributes

to the degree of 2 vertices, the number of edges in the shortest cycle is 5c

Step 5: Since each edge is shared by exactly 2 vertices, the total number

of edges in the graph is at most 1

2·12 ·(12 −1) = 66. This contradicts the fact

that the graph has only 17 edges.

Step 6: Therefore, our initial assumption is incorrect. Hence, Gmust

contain a cycle of length at most 4.

Thus, we have proven that the graph Gcontains a cycle of length at most 4.

Question 35

Question

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

a cycle of length at most 5.

Solution

To prove that Gcontains a cycle of length at most 5, we will use the concept of

the pigeonhole principle.

Step 1: Determine the maximum number of edges in a tree with

10 vertices A tree with nvertices has n−1 edges. So, in our case, a tree with

10 vertices has 9 edges.

Step 2: Find the number of edges in excess of a tree in GSince G

has 16 edges and a tree with 10 vertices has 9 edges, there are 16 −9 = 7 edges

in Gthat are not present in a tree with 10 vertices.

Solution

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

fact that the average degree of the vertices in Gis at least 3.

Step 1: Calculate the average degree of the vertices. Let vbe the

number of vertices in the graph Gand ebe the number of edges in G. The

average degree ¯

dof the vertices is given by ¯

d=2e

Substitute v= 10 and e= 18 into the formula:

d=2×18

10 = 3.6.

Step 2: At least one vertex has degree 3 or less. If all vertices in

Ghad degree 4 or more, the sum of all degrees would be at least 4 ×10 = 40,

which is impossible as there are only 18 edges in total. Therefore, at least one

vertex must have degree 3 or less.

Step 3: Find a cycle of length at most 4. Since there is a vertex with

degree 3 or less, we can start at that vertex and trace a path through three

more vertices, forming a cycle of length at most 4. Thus, we have shown that

Gcontains a cycle of length at most 4.

Question 3

Question

Let Gbe a connected graph with 12 vertices and 19 edges. What is the maximum

number of edges that can be added to Gwithout disconnecting it?

Solution

To find the maximum number of edges that can be added to Gwithout discon-

necting it, we need to determine the minimum number of edges required for G

to remain connected.

Step 1: Determine the minimum number of edges required for a connected

graph with 12 vertices. For a connected graph with nvertices, we need at least

n−1 edges to ensure connectivity. Therefore, for a connected graph with 12

vertices, we need at least 12 −1 = 11 edges.

Step 2: Determine the maximum number of edges that can be added with-

out disconnecting G. Given that Galready has 19 edges, we can add at most

12 edges (total vertices - 1) without disconnecting the graph.

Therefore, the maximum number of edges that can be added to Gwithout

disconnecting it is 12.

Question 4

Question

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

a cycle of length at least 4.

Solution

Let nbe the number of vertices in graph G.

Step 1: Determine the number of edges in a tree with nvertices. In a tree

with nvertices, there are n−1 edges. This can be proven by induction on the

number of vertices.

Step 2: Calculate the maximum number of edges in a connected graph with

10 vertices. For a connected graph with nvertices, the maximum number of

edges is given by n(n−1)/2. Therefore, for n= 10 vertices, the maximum

number of edges is 10(10 −1)/2 = 45.

Step 3: Determine the minimum number of edges needed for a cycle of

length 4 in a connected graph with 10 vertices. To form a cycle of length 4 in

a connected graph, we need at least 4 edges.

Step 4: Establish a contradiction. If Gdoes not contain a cycle of length

at least 4, then it is a tree. Since Ghas 18 edges, which is greater than the

maximum number of edges in a tree with 10 vertices (17 edges), this leads to a

contradiction.

Step 5: Conclude. Therefore, if Gis a connected graph with 10 vertices

and 18 edges, it must contain a cycle of length at least 4.

Question 5

Question

Let Gbe a connected graph with nvertices where every vertex has degree at

least n

2. Show that Gis a cycle.

Solution

To prove that Gis a cycle, we will first establish some properties of the graph

and then show that it must be a cycle.

Step 1: Show that Ghas exactly one simple cycle.

Since Gis connected with nvertices, it must have a simple cycle by the Cycle

Existence Lemma in Graph Theory. Let Cbe a simple cycle in Gwith the

maximum number of vertices.

Step 2: Show that Cspans all vertices in G.

Assume there exists a vertex uin Gthat is not part of the cycle C. Every vertex

in Cis connected to at least n

2other vertices. Since there are only nvertices in

total, there must be a vertex in Cconnected to u. This creates a cycle longer

than C, contradicting the maximality of C. Hence, every vertex in Gmust be

in C.

Step 3: Show that Gis a cycle.

Since every vertex in Gis in the cycle C, and Cis a simple cycle with all n

vertices of G,Gmust be the cycle C. Therefore, Gis a cycle.

Thus, we have shown that if a connected graph with nvertices has every

vertex with degree at least n

2, then the graph must be a cycle.

Question 6

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 a graph is Hamiltonian, we must show that there exists a Hamil-

tonian cycle in the graph, i.e., a cycle that visits each vertex exactly once.

Step 1: If Gis a complete graph, then Gis Hamiltonian. Let Kndenote

the complete graph with nvertices. It is known that Knis Hamiltonian for

n≥3.

Step 2: Let Gbe a connected graph with nvertices and each vertex has

degree at least n

2. Since Gis not complete, there exists non-adjacent vertices

uand vin G. Let Ube the set of vertices adjacent to uand Vbe the set of

vertices adjacent to v.

Step 3: Since Gis connected, Uand Vare non-empty. If |U|+|V| ≥ n

(i.e., there are enough vertices to form a Hamiltonian cycle using uand v), then

we can construct a Hamiltonian cycle.

Step 4: Suppose |U|+|V|< n. Since every vertex has degree at least n

then |U|+|V| ≥ n−1. Without loss of generality, assume |U| ≤ n

2−1. Then

|V| ≥ n− |U|> n −(n

2−1) = n

2+ 1.

Step 5: Consider a graph Hobtained from Gby removing uand all edges

incident to u. Since |V| ≥ n

2+ 1, Hhas at least n

2+ 1 vertices. Every vertex in

Hhas degree at least n

Step 6: By induction hypothesis, Hcontains a Hamiltonian cycle. Adding

vertex uand the edges between uand the vertices in Vto the Hamiltonian cycle

in Hforms a Hamiltonian cycle in G.

Therefore, if every vertex in a connected graph Gwith nvertices has degree

at least n

2, then Gis Hamiltonian.

Question 7

Question

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

a cycle.

Solution

To prove that a connected graph Gwith 12 vertices and 15 edges contains a

cycle, we will make use of the fact that in a connected graph with more edges

than vertices, there must be at least one cycle.

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

the vertices. The Handshaking Lemma states that in any graph, the sum of the

degrees of all vertices is equal to twice the number of edges. Therefore, for a

graph with 12 vertices and 15 edges, the sum of the degrees is 2 ·15 = 30. Since

the graph is connected, the average degree of the vertices in Gis 30

12 = 2.5.

Step 2: Deduce that there must be at least one vertex with degree at least

3. If all vertices in Ghad degree at most 2, the sum of the degrees would be at

most 2 ·12 = 24, which is less than the actual sum of degrees (30). Therefore,

there must be at least one vertex with degree at least 3.

Step 3: Use the fact that a connected graph with more edges than vertices

contains a cycle. Since Ghas 15 edges and 12 vertices, which includes at least

one vertex with degree at least 3, there must be at least one cycle in G.

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

15 edges contains a cycle.

Question 8

Question

A simple graph Ghas 10 vertices, each with degree 4. Prove that Gcontains a

cycle of length 3.

Solution

Let’s prove this by contradiction.

Step 1: Assume that there is no cycle of length 3 in the graph.

Step 2: Since every vertex in Ghas degree 4, each vertex is adjacent to 4

other vertices in the graph.

Step 3: Consider a vertex vin G. Since there is no cycle of length 3, the 4

neighbors of vmust be pairwise distinct.

Step 4: Therefore, the 4 neighbors of vcannot have any edges between

them (otherwise, a cycle of length 3 would exist).

Step 5: This means that these 4 neighbors of vare all distinct and form an

independent set in G. Since Ghas 10 vertices and each vertex has degree 4, we

have used up all the remaining 6 vertices.

Step 6: Constructing the graph in this way, we see that there is no way to

add edges between the remaining 6 vertices to form a cycle of length 3 without

violating the condition that there is no cycle of length 3.

Step 7: This is a contradiction, as the initial assumption led to an impossi-

bility. Therefore, our assumption that there is no cycle of length 3 in the graph

must be false.

Step 8: Hence, we have proved that a simple graph Gwith 10 vertices, each

with degree 4, must contain a cycle of length 3.

Question 9

Question

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

a cycle of length at most 4.

Solution

To prove that Gcontains a cycle of length at most 4, we will proceed by con-

tradiction:

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

Since Gis connected with 10 vertices, 13 edges, and does not contain a cycle

of length at most 4, the graph must be a tree. By the property of a tree, a tree

with nvertices always has n−1 edges.

Step 2: Count the number of edges in the tree.

Since Gis a tree with 10 vertices, it must have 10 −1 = 9 edges.

Step 3: Contradiction.

We are given that Ghas 13 edges - a contradiction to our assumption that

Gis a tree. Therefore, our assumption that Gdoes not contain a cycle of length

at most 4 is incorrect.

Since our assumption led to a contradiction, we conclude that Gmust contain

a cycle of length at most 4.

Question 10

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. Suppose Gis a connected graph with nvertices and medges,

where m<n−1.

Step 1: Recall the Handshaking Lemma, which states that the sum of the

degrees of all vertices in a graph is equal to twice the number of edges. Since G

is connected, the sum of the degrees of all vertices is at least 2(n−1).

Step 2: Consider the sum of the degrees of all vertices in G. Let d1, d2, ..., dn

be the degrees of the nvertices in G. Then we have:

d1+d2+· · · +dn≥2(n−1)

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

in Gis equal to 2m. So we have:

2m=d1+d2+· · · +dn

Step 4: Combining the inequalities from Steps 1 and 2, we get:

2(n−1) ≤2m

Step 5: Since m<n−1, we have 2(n−1) ≤2m < 2(n−1), which is

a contradiction. Therefore, our initial assumption that Gis connected when

m<n−1 is false.

Step 6: Hence, if m<n−1, then Gis not connected.

Question 11

Question

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

a cycle.

Solution

Step 1: Let’s start by assuming that Gdoes not contain a cycle. Since Gis

connected, it must be a tree.

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. Since Gis a tree

with 10 vertices, the sum of degrees of all vertices is 2(10 −1) = 18.

Step 3: Since Ghas 13 edges, the sum of degrees of all vertices must be at

least 26. Since 18 ¡ 26, this is a contradiction.

Step 4: Therefore, our initial assumption that Gdoes not contain a cycle is

incorrect. Hence, Gmust contain a cycle.

Question 12

Question

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

a cycle of length at most 6.

Solution

To prove that Gcontains a cycle of length at most 6, we will use a proof by

contradiction.

Step 1: Assume that Gdoes not contain any cycle of length at most 6.

Step 2: By the handshake lemma, the sum of the degrees of all vertices in

Gis twice the number of edges. Since Ghas 10 vertices and 15 edges, the sum

of the degrees of all vertices is 2 ×15 = 30.

Step 3: Since Gis connected, there is at least one vertex of degree at least

1. Let’s consider the shortest path between two such vertices.

Step 4: Suppose the shortest path between two vertices of degree at least 1

is of length d, where d > 6. Since Ghas no cycle of length at most 6, this path

must be a simple path.

Step 5: Along the path, each intermediate vertex (except the start and end

vertices) should have degree 2 (since otherwise, we could shortcut the path and

reduce its length).

Step 6: However, if the path has length d > 6, it will have d+ 1 vertices

including the endpoints. This would contribute at least 2(d+ 1) = 2d+ 2 >

2∗6 = 12 to the sum of degrees, which contradicts the fact that the sum of

degrees is 30.

Step 7: Therefore, our initial assumption that Gdoes not contain any cycle

of length at most 6 must be false. Hence, Gcontains a cycle of length at most

Question 13

Question

Let Gbe a connected graph with 12 vertices and 16 edges. If Ghas exactly one

cycle, how many vertices and edges does this cycle have?

Solution

Let vbe the number of vertices in the cycle and ebe the number of edges in the

cycle. Since Ghas 12 vertices and 16 edges, by Euler’s formula for connected

graphs we have v−e+ 1 = 12 −16 + 1 = −3.

Since Ghas exactly one cycle, all other edges must be part of the spanning

tree. Therefore, the total number of edges in the graph is v−1. This gives us

the equation v−1 = 16.

Solving the system of equations v−e+ 1 = −3 and v−1 = 16, we find

v= 17 and e= 16. Thus, the cycle in Ghas 17 vertices and 16 edges.

Question 14

Question

Let Gbe a simple graph with 10 vertices and 20 edges. Prove that Gcontains

a cycle of length at most 4.

Solution

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

Principle.

Step 1: Computing the average degree Since Ghas 10 vertices and 20

edges, the average degree of the vertices in Gis 2 ×20

10 = 4. This means there

must be at least one vertex with degree less than or equal to 4.

Step 2: Constructing a subgraph Let vbe a vertex in Gwith degree

less than or equal to 4. Removing vand its incident edges from G, we obtain a

subgraph G′with 9 vertices and at most 19 edges.

Step 3: Applying the Pigeonhole Principle In the graph G′, the aver-

age degree of the vertices is at most 2 ×19

9≈4.22. By the Pigeonhole Principle,

there must exist a vertex uwith degree at most 4 in G′.

Step 4: Finding a short cycle Since uhas degree at most 4 in G′, there

are at most 4 vertices adjacent to u. If any two of these vertices are adjacent

in G′, then a cycle of length at most 4 is formed. If no such pair exists, then u

must have at least 5 neighbors forming a subgraph K5, which contains a cycle

of length 3.

Therefore, we have shown that Gcontains a cycle of length at most 4.

Question 15

Question

Let Gbe a simple undirected 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 Pigeonhole

Principle.

Step 1: Determine the maximum number of edges in a tree. A tree

with 10 vertices has 9 edges. This is because a tree with nvertices has n−1

edges.

Step 2: Calculate the number of edges exceeding a tree. Since G

has 15 edges, there are 6 edges more than a tree with 10 vertices.

Step 3: Consider the possible connections of the extra edges. Each

extra edge connects two vertices, which either form a cycle or extend an existing

cycle.

Step 4: Use the Pigeonhole Principle. A cycle with 4 or more vertices

must have at least 4 edges. Since there are 6 extra edges, at least one of the

extra edges completes a cycle of length at least 4.

Therefore, Gcontains a cycle of length at least 4.

Question 16

Question

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

a cycle of length at most 4.

Solution

To show that Gcontains a cycle of length at most 4, we will use the Pigeonhole

Principle.

1. Let nbe the number of vertices in G, and mbe the number of edges in

G. In this case, n= 10 and m= 18.

2. By the Handshaking Lemma, the sum of degrees of all vertices in a graph

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

in Gis 2m= 36.

3. Since each vertex in Gis connected to at least one other vertex (as Gis

connected), the average degree of a vertex in Gis 2m

n=36

10 = 3.6. This

means there exists at least one vertex with degree at most 4.

4. Select a vertex vin Gwith degree at most 4. Consider the vertices adjacent

to v- there are at most 4 such vertices. Let these vertices be u1, u2, u3, u4.

5. If any of the vertices uiare connected to v(creating a cycle of length 3),

then we are done. Otherwise, each uimust be connected to at least one

other uj(i=j) to avoid creating a cycle of length 2.

6. By the Pigeonhole Principle, at least two of the vertices uiare adjacent

to the same vertex uj(i=j). This creates a cycle of length at most 4.

Therefore, we have shown that Gcontains a cycle of length at most 4.

Question 17

Question

Let Gbe a simple, 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 Pigeonhole

Principle.

Step 1: Find the minimum number of edges needed for Gto guar-

antee a cycle of length 3. For a graph to guarantee a cycle of length 3, it

must contain 3 vertices connected by edges. The minimum number of edges

needed for this is 3

2= 3.

Step 2: Consider the remaining 7 vertices in G.Since Ghas 10

vertices and 15 edges, there are 7 remaining vertices after the 3 vertices in our

minimum cycle of length 3.

Step 3: Apply the Pigeonhole Principle. Divide the 7 remaining ver-

tices into 3 groups, where each group contains at least 3 vertices. By the Pi-

geonhole Principle, at least one group must contain 4 vertices.

Step 4: Create a cycle of length at least 4. In the group with 4 vertices,

there must be at least 3 edges connecting these vertices. Adding these edges to

the minimum cycle of length 3, we form a cycle of length at least 4.

Therefore, we have shown that any simple, connected graph Gwith 10 ver-

tices and 15 edges contains a cycle of length at least 4.

Question 18

Question

Let Gbe a connected graph with 10 vertices where each vertex has degree at

least 3. Prove that Gcontains a cycle of length at least 4.

Solution

Let’s prove this by contradiction.

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

Step 2: Since Gis connected and does not contain a cycle of length at least

4, each face in the planar representation of Gmust have length 3.

Step 3: By Euler’s formula, v−e+f= 2, where vis the number of vertices,

eis the number of edges, and fis the number of faces. Since Gis connected

and planar, e≤3v−6 and f≤2v−4.

Step 4: On the other hand, the sum of the degrees of the vertices in a graph

is equal to twice the number of edges. Since each vertex in Ghas degree at least

3, the sum of the degrees of the vertices is at least 3v. Therefore, 2e≥3v.

Step 5: Combining the inequalities from Step 3 and Step 4, we have: 3v≤

2e≤6v−12

0≤3v−12

12 ≤3v

4≤v

Step 6: Since Ghas 10 vertices, we have reached a contradiction. Therefore,

our initial assumption that Gdoes not contain a cycle of length at least 4 is

false.

Step 7: Hence, we conclude that Gmust contain a cycle of length at least

Question 19

Question

Let Gbe a simple connected graph with 11 vertices and 17 edges. Prove that

Gcontains a cycle of length at most 5.

Solution

Step 1: We begin by considering the case where Gcontains a vertex of degree at

most 2. If there exists a vertex of degree 1 in G, then removing that vertex would

reduce the number of edges by 1 but keep the graph connected, creating a cycle

of length 1. Similarly, if there exists a vertex of degree 2 in G, then removing

that vertex together with its incident edges would preserve connectivity while

creating a cycle of length 2.

Step 2: Now, assume that all vertices in Ghave degree at least 3. Using 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. Therefore, the sum of the degrees

of all vertices in Gis 2 ×17 = 34.

Step 3: Since Ghas 11 vertices and each vertex has degree at least 3, the

sum of the degrees of all vertices must be at least 11 ×3 = 33. This implies

that the sum of the degrees of all vertices is exactly 34.

Step 4: We observe that it is not possible for all vertices in Gto have degree

exactly 3 because that would imply a total degree of 11 ×3 = 33, which is less

than 34. Hence, there must exist at least one vertex in Gwith degree greater

than 3.

Step 5: Consider a vertex vin Gwith degree at least 4. Since Gis connected

and vhas at least 4 neighbors, there must exist at least two distinct neighbors

of vthat are adjacent to each other. Let these neighbors be uand w, where u

and ware distinct vertices.

Step 6: The existence of edges uv and vw along with the edge vw creates

a cycle of length at most 5 in G(specifically, the cycle formed by the vertices

u, v, w). Therefore, we have shown that Gmust contain a cycle of length at

most 5.

Question 20

Question

Let Gbe a connected graph with 12 vertices and 17 edges. If Ghas exactly two

vertices of degree 3 and all other vertices of degree 4, how many cycles of length

4 does Gcontain?

Solution

Let nbe the number of cycles of length 4 in G.

Step 1: Find the total degree sum of the graph. Since the sum of the

degrees of the vertices in a graph is twice the number of edges, we have:

2|E|=Xdegree of v

2×17 = 12 ×4+2×3

34 = 48 + 6

34 = 54

Step 2: Deduce a contradiction. Since the total degree sum is not equal to

2 times the number of edges, we have a contradiction. Therefore, there are no

cycles of length 4 in the graph G.

Question 21

Question

Let Gbe a simple 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 assume the contrary

and reach a contradiction using the Handshaking Lemma and the Cycle Lemma.

Step 1: Calculate the minimum number of edges a graph with

10 vertices can have. The minimum number of edges in a simple connected

graph with 10 vertices occurs when the graph is a tree. A tree with nvertices

has n−1 edges. Thus, a graph with 10 vertices must have at least 9 edges.