MATH 350 - DISCRETE MATHEMATICS Graph Theory Question Bank Set 2

MATH 350 - DISCRETE

MATHEMATICS - Graph Theory

Question Bank - Set 2

Liberty University

Question 1

Question

Let Gbe a connected graph with 10 vertices and 12 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 proof by

contradiction.

Step 1: Assume for contradiction that Gdoes not contain a cycle of length

at least 4.

Step 2: Since Gis connected and has 10 vertices, the maximum number of

edges in Gis given by |E|=|V| − 1 = 9. However, we are given that Ghas 12

edges, which contradicts the claim that Gdoes not contain a cycle of length at

least 4.

Step 3: Therefore, our assumption that Gdoes not contain a cycle of length

at least 4 is false. Hence, Gmust contain a cycle of length at least 4.

Thus, we have proven that any connected graph with 10 vertices and 12

edges must contain a cycle of length at least 4.

Question 2

Question

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

a cycle of length at least 4.

Solution

Let’s prove this by contradiction. Assume that Gis a connected graph with 10

vertices and 14 edges that does not contain a cycle of length at least 4.

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

A tree with nvertices has n−1 edges. So, a tree with 10 vertices can have a

maximum of 10 −1 = 9 edges.

Step 2: Obtain the difference between the number of edges in Gand the

maximum number of edges in a tree with 10 vertices. Since Ghas 14 edges and

the maximum number of edges in a tree with 10 vertices is 9, the difference is

14 −9 = 5.

Step 3: Understand the structure of the graph. Since Gis connected and

does not contain a cycle of length at least 4, the graph is a tree or a forest of

trees.

Step 4: Analyze the possible structures of the graph. If Gis a tree, it

cannot have 14 edges, contradicting the given conditions. Therefore, Gmust be

a forest of trees with components.

Step 5: Count the total number of components in the forest. Since Ghas

10 vertices and each component of a disconnected graph is a tree, and a tree

has n−1 edges, the total number of components in the forest must be 10 - 1 =

Step 6: Count the total number of edges in the forest. Since each tree

component has at most n−1 edges, the total number of edges in the forest

must be at most 9 ×9 = 81.

Step 7: Determine the contradiction. Given that Ghas 14 edges, this

contradicts the fact that the total number of edges in the forest is at most 81.

Thus, our assumption that Gdoes not contain a cycle of length at least 4 must

be false. Hence, Gmust contain a cycle of length at least 4.

Question 3

Question

Let Gbe a simple graph with 10 vertices, where the degree of each vertex is

either 3 or 7. Prove that Gmust contain a cycle of length 3.

Solution

Step 1: Let vbe a vertex with degree 7. Since vhas 7 neighbors, and each

vertex has a degree of 3 or 7, then all of v’s neighbors must have a degree of 3.

Otherwise, if one of v’s neighbors had a degree of 7, then that neighbor would

have more than 7 neighbors, contradicting the fact that it’s in a simple graph.

Step 2: Consider the graph induced by vand its 7 neighbors. Since vhas

7 neighbors, we have a graph with 8 vertices (including v) and 21 edges (since

each neighbor of vhas degree 3). By the Pigeonhole Principle, this graph must

contain a cycle of length 3, as there are 8 vertices and 21 edges.

Step 3: Therefore, in our original graph G, which has 10 vertices and vertices

with degrees 3 or 7, there must be a vertex with degree 7 that is part of a cycle

of length 3. This completes the proof.

Question 4

Question

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

at least one cycle.

Solution

To prove that Gcontains at least one cycle, we will make use of the fact that a

connected graph with nvertices and nedges contains a cycle.

Step 1: Determine the number of components in G.

Since Gis connected, there is only one component.

Step 2: Apply the cycle condition.

By the cycle condition, a connected graph with nvertices and nedges con-

tains a cycle.

In this case, Ghas 10 vertices and 15 edges, so n= 10 and m= 15. Since

m>n−1, there must be at least one cycle in G.

Therefore, we have proved that Gcontains at least one cycle.

Question 5

Question

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

a cycle.

Solution

To prove that Gcontains a cycle, we will use the fact that a connected graph

with nvertices and nedges contains a cycle.

Step 1: Identify the properties of the given graph G.

Since Gis a connected graph with 10 vertices and 15 edges, we can denote

n= 10 and m= 15, meaning that n=m.

Step 2: Use the fact that a connected graph with nvertices and nedges

contains a cycle.

By the above fact, since Gis connected with 10 vertices and 15 edges (n=

10 = m), Gmust contain a cycle.

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

15 edges contains a cycle.

Question 6

Question

Let Gbe a connected graph with 10 vertices, 15 edges, and exactly 3 vertices

of degree 5. Prove that Gcontains at least one cycle.

Solution

To prove that the graph Gcontains at least one cycle, we will use the fact that

connected graphs with nvertices and medges must contain at least one cycle

if m>n. We will first show that Gsatisfies this condition.

Step 1: Determine the total sum of degrees in G. Since Gis a graph with

10 vertices and 3 vertices of degree 5, we have:

Xdegrees = 2 ×number of edges = 2 ×15 = 30

Step 2: Find the sum of degrees of the remaining vertices. Let v1, v2, v3be

the vertices of degree 5 and v4, v5, ..., v10 be the remaining vertices. The sum of

the degrees of vertices v4to v10 is:

i=4

degree(vi) = 30 −3×5 = 15

Step 3: Determine the minimum possible degree of the remaining vertices.

Since a connected graph has at least one edge incident to each vertex, the

minimum degree of the remaining vertices is 1. Thus, the sum of the degrees of

the remaining vertices is at least 7 ×1 = 7.

Step 4: Sum of degrees is greater than or equal to 15 + 7 = 22. Therefore,

the sum of the degrees of all vertices in Gis at least 22, which means there are

at least 22 edges incident to the vertices in G.

Step 5: Since Ghas 15 edges, m > n condition is satisfied. There are 15

edges in Gand 10 vertices, so m= 15 > n = 10. Therefore, by the theorem

mentioned at the beginning, Gmust contain at least one cycle.

Hence, we have proven that graph Gcontains at least one cycle.

Question 7

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 Gis connected Assume Gis connected even though

m<n−1.

Step 2: Relationship between edges and vertices in a connected

graph In a connected graph with nvertices, the minimum number of edges

required to connect all vertices is n−1. This means that if m < n −1, there

are not enough edges in Gto connect all nvertices.

Step 3: There must be at least two separate components Since there

are not enough edges to form a single connected component with nvertices,

there must be at least two separate components in G. Each component itself is

connected internally but not to other components.

Step 4: Each component is a connected subgraph Since each compo-

nent is connected internally, we can consider each component separately. How-

ever, if we consider all components together, the graph Gis not connected.

Step 5: Contradiction Our assumption that Gis connected leads to a

contradiction when m<n−1. Therefore, Gcannot be connected if m<n−1.

Thus, if m<n−1, then Gis not connected.

Question 8

Question

Prove that in any group of six people, there are either three people who are all

mutual friends or three people who are all mutual strangers.

Solution

Step 1: Consider a person A in the group of six people. Step 2: There are five

other people in the group. By the Pigeonhole Principle, at least three of them

must either all know A or all not know A. Step 3: If three people know A, then

either they are mutual friends or not. Step 4: If they are mutual friends, then A

and these three people form a group of four mutual friends. Step 5: If they are

mutual strangers, then there is a group of three mutual strangers in the group.

Step 6: If three people do not know A, then they either all know each other or

are mutual strangers. Step 7: Following the same arguments as in Steps 4 and

5, we can conclude that there are either three mutual friends or three mutual

strangers among these three people. Step 8: Thus, in any group of six people,

there are either three people who are all mutual friends or three people who are

all mutual strangers.

Question 9

Question

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

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

Solution

Step 1: Since Gis connected with 11 vertices, it must have at least 11

2= 5.5

edges by the handshake lemma. Thus, Ghas at least 6 edges.

Step 2: Since each vertex has degree at least 4, the total number of degrees

in Gis at least 4 ×11 = 44.

Step 3: Let e(G) be the number of edges in Gand f(G) be the number of

faces in the planar representation of G. By Euler’s formula, v−e+f= 2, we

have 11 −e(G) + f(G) = 2.

Step 4: Since the graph is connected, the planar representation has 1 con-

nected component. Therefore, f(G) = 1.

Step 5: Substituting f(G) = 1 into Euler’s formula, we get 11−e(G)+ 1 = 2

which simplifies to e(G)≥10.

Step 6: Since Ghas at least 6 edges, there must be at least one cycle present

in G. Let Cbe the cycle with the fewest number of edges.

Step 7: Assume for the sake of contradiction that Chas length 3. Then C

would consist of 3 edges and 3 vertices, all of which have degree exactly 2. This

contradicts the given condition that each vertex has degree at least 4.

Step 8: Therefore, the cycle Cmust have length at least 4. This completes

the proof that Gcontains a cycle of length at least 4.

Question 10

Question

Let Gbe a connected graph with 10 vertices and 20 edges. Prove that Gis not

a tree.

Solution

To prove that Gis not a tree, we will show that it contains at least one cycle.

Step 1: Recall that a tree is a connected graph with no cycles.

Step 2: Use the Handshaking Lemma to find the sum of the degrees of the

vertices in G. Since Ghas 10 vertices, the sum of the degrees is 2|E|= 40.

Step 3: Assume for the sake of contradiction that Gis a tree.

Step 4: In a tree with nvertices, there are n−1 edges. Since Ghas 20

edges, it cannot be a tree with 10 vertices.

Step 5: Therefore, the assumption that Gis a tree leads to a contradiction.

Step 6: Thus, Gis not a tree, and hence it must contain at least one cycle.

Question 11

Question

Let Gbe a simple graph with 10 vertices, 23 edges, and no cycles of length 3.

Determine the maximum number of cycles that Gcan have.

Solution

To find the maximum number of cycles in a graph G, we first need to determine

how many edges can be in each cycle. Since Ghas no cycles of length 3, the

minimum cycle length in Gis 4.

Step 1: Counting edges in a cycle

Let mbe the number of edges in a cycle. For a cycle of length k, there are

kedges. Since the minimum cycle length in Gis 4, we have m≥4.

Step 2: Relationship between edges and vertices in a cycle

For a cycle of length k, there are kvertices and kedges. Each vertex in

the graph can be the starting point of at most 2 cycles (one clockwise, one

counterclockwise). Therefore, the number of cycles in Gis at most half the

number of edges in the graph.

Step 3: Calculating the maximum number of cycles

We are given that Ghas 10 vertices and 23 edges. We have m≥4 for the

cycles. The maximum number of cycles is given by:

Maximum number of cycles ≤23

Step 4: Final calculation

Maximum number of cycles ≤5.75 ≈5

Therefore, the maximum number of cycles that Gcan have is 5.

Question 12

Question

Let Gbe a connected graph with nvertices and medges. If every vertex of G

has degree at least n

2, prove that Gis Hamiltonian.

Solution

We will prove that a connected graph Gwith nvertices and at least n

2degree

for each vertex is Hamiltonian by contradiction.

Step 1: Assume Gis not Hamiltonian.

If Gis not Hamiltonian, it must have a vertex of degree less than n

2due to

the Dirac’s theorem. Let vbe a vertex of Gwith degree less than n

2. Let ube

a neighbor of v.

Step 2: Adding an edge between uand vdoes not create a cycle in G.

If we add an edge between uand v, it does not create a cycle as ualready

has degree greater than n

2. Now, degrees of uand vare both greater than n

Step 3: Since adding an edge between uand vdoes not create a cycle, we

can continue this process with other vertices in the graph.

Continuing this process, we will eventually create a Hamiltonian cycle in

G, as each step maintains connectivity and adds edges between non-adjacent

vertices. This contradicts our assumption that Gis not Hamiltonian.

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

if every vertex of a connected graph Gwith nvertices has a degree of at least

2, then Gis Hamiltonian.

Question 13

Question

Let Gbe a connected graph with 10 vertices and 17 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 it has

a subgraph that must contain such a cycle.

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

cycle of length k.For a cycle of length k, we need at least kedges. Thus, for

a cycle of length at most 4, we need at least 4 edges.

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

10 vertices can have. A complete graph K10 with 10 vertices has 10

2= 45

edges. Since Ghas 17 edges, it must be a subgraph of K10 .

Step 3: Consider the complementary graph G.The complementary

graph Gof Ghas the same vertices as Gbut has an edge between two vertices

if and only if they are not adjacent in G. Therefore, Ghas 45 −17 = 28 edges.

Step 4: Show that Gcontains a 5-clique. If Gdoes not contain a 5-

clique, then the largest clique in Ghas at most 4 vertices. By Tur´an’s theorem,

the number of edges in Gis at most 1−1

4−110

2= 28, which contradicts the

fact that Ghas 28 edges.

Since Gcontains a 5-clique, Gmust contain an induced subgraph that is a

5-independent set. This implies that Ghas a cycle of length at most 4.

Question 14

Question

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

contain a cycle.

Solution

Step 1: Let’s start by assuming the graph Gdoes not contain a cycle. This

means that Gis a tree since a connected acyclic graph is a tree. Since Ghas 10

vertices, it must have 9 edges to be a tree.

Step 2: However, we are given that Ghas 20 edges, which is more than

the maximum number of edges in a tree with 10 vertices. This contradicts our

assumption that Gis a tree.

Step 3: Therefore, our assumption that Gdoes not contain a cycle must be

false. Hence, Gmust contain at least one cycle.

Question 15

Question

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

a cycle of length at most 4.

Solution

To prove that there exists a cycle of length at most 4 in the graph G, we will

make use of the Pigeonhole Principle.

Step 1: Use the Pigeonhole Principle to show that there must be a vertex

of degree at least 3 in G. Since Gis a connected graph with 8 vertices and 12

edges, the average degree of a vertex in Gis 2·12

8= 3. Therefore, there must

exist a vertex in Gwith degree at least 3.

Step 2: Consider the neighbors of this vertex with degree at least 3. Let v

be a vertex in Gwith degree at least 3. Since Gis connected, vmust have at

least 3 neighbors.

Step 3: Use the Pigeonhole Principle again to show that there exists a cycle

of length at most 4. Consider the neighbors of vertex v. Since vhas at least 3

neighbors, by the Pigeonhole Principle, there must be at least 2 neighbors of v

that are the same. This forms a cycle of length at most 4 by including vtwice.

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

at most 4.

Question 16

Question

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

Gcontains a cycle of length at least 4.

Solution

We can prove this by contradiction. Assume that Gdoes not contain a cycle of

length at least 4.

Step 1: Counting the edges in a tree.

Since Gis connected and has 10 vertices, it must be a tree if it does not contain

a cycle of length at least 4. By the property of trees, a tree with nvertices

has n−1 edges. Therefore, Gmust have 9 edges (20 - 9 = 11 edges would be

necessary to form a cycle of length 4).

Step 2: Counting the edges in a graph.

Since Ghas 20 edges, which is greater than the 9 edges in a tree with 10 vertices,

Gmust contain at least one cycle. Let Cbe any cycle in G.

Step 3: Finding a cycle of length at least 4.

Since Cis a cycle, it must have at least 3 edges. If the cycle Chas exactly

3 edges, then we can add any edge not in Cto create a cycle of length 4,

contradicting our assumption. Therefore, Cmust have at least 4 edges, proving

that Gcontains a cycle of length at least 4.

Since the assumption led to a contradiction, the original statement must be

true. Therefore, Gcontains a cycle of length at least 4.

Question 17

Question

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

a cycle of length at most 4.

Solution

To solve this problem, we will use the Pigeonhole Principle.

Step 1: Let’s assume for the sake of contradiction that Gdoes not contain

a cycle of length at most 4.

Step 2: Since Gis connected with 10 vertices, there must exist a path of

length at most 9 (since the maximum path length from one vertex to another

is the total number of vertices minus 1).

Step 3: Let pbe the longest path in G. By the assumption, pmust have a

length of exactly 9.

Step 4: Since pis the longest path, the two endpoints of pcannot have

any common neighbors other than their shared endpoint. Otherwise, it would

create a longer path contradicting the assumption.

Step 5: Since Gis connected, each vertex in Gmust have a degree of at

least 1. Therefore, each vertex in p(except the endpoints) must have a neighbor

outside of p.

Step 6: Since Ghas 10 vertices, pconsists of 10 vertices including endpoints.

This means there are no vertices remaining to form any new paths of length 9

that are disjoint from p.

Step 7: Now, let’s count the total number of edges. The 9 vertices in p

contribute 8 edges, and the remaining 10 vertices must contribute at least 10

more edges (as each vertex must have a minimum degree of 1).

Step 8: As we counted 8 edges in p, and there must be at least 10 edges

outside of p, this totals to at least 18 edges. But this contradicts the given total

of 18 edges in G. Hence, our assumption that Gdoes not contain a cycle of

length at most 4 is incorrect.

Step 9: Therefore, we conclude that Gmust contain a cycle of length at

most 4.

Question 18

Question

Let Gbe a connected graph with 12 vertices and 25 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: Determine the possible number of edges in a cycle of length at least

Let Cbe a cycle of length at least 5 in G. Then Chas at least 5 vertices and

5 edges. Each additional vertex added to Ccontributes 1 new edge. Therefore,

if Chas k≥5 vertices, then Chas kedges.

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

and no cycle of length at most 4.

Assume for the sake of contradiction that Ghas no cycle of length at most

4. Then the longest cycle in Ghas length at least 5. By Step 1, every cycle

of length at least 5 has exactly the same number of edges as vertices. So,

each cycle of length at least 5 contributes at least 5 edges. Since Ghas 12

vertices, the maximum number of edges in Gwith no cycle of length at most 4

is 5 ×12

5= 5 ×2 = 10.

Step 3: Observe the number of edges in G.

Given that Ghas 25 edges, which is greater than the maximum number of edges

(10) calculated in Step 2, there must be at least one cycle of length at most 4

in G.

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

25 edges must contain a cycle of length at most 4.

Question 19

Question

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

Hamiltonian cycle, then Gmust satisfy the condition k≥n.

Solution

To prove that if Ghas a Hamiltonian cycle, then Gmust satisfy the condition

k≥n, we will use a proof by contradiction.

Step 1: Assume the opposite Assume there exists a connected graph G

with nvertices and kedges (k < n) that has a Hamiltonian cycle.

Step 2: Hamiltonian cycle property By definition, a Hamiltonian cycle

is a cycle in a graph that visits each vertex exactly once and returns to the

starting vertex.

Step 3: Edge-counting on the cycle Since Ghas a Hamiltonian cycle,

we know that every vertex in the cycle is connected by an edge to the next

vertex in the cycle.

If Gcontains a Hamiltonian cycle, the number of edges in the cycle must be

at least n(since there are nvertices in the cycle).

Step 4: Contradiction If Ghas a Hamiltonian cycle, then the number of

edges (k) in the graph must be at least n. However, we assumed that k < n,

which contradicts our initial assumption.

Therefore, our assumption that there exists a connected graph Gwith n

vertices and kedges (k < n) that has a Hamiltonian cycle is false. This implies

that if Ghas a Hamiltonian cycle, then Gmust satisfy the condition k≥n.

Question 20

Question

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

a cycle of length at most 3.

Solution

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

Pigeonhole Principle.

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

is connected and has 10 vertices, the maximum number of edges in a tree with

10 vertices is 10 −1 = 9. Therefore, Gcontains at least 19 −9 = 10 edges that

form cycles.

Step 2: Consider vertices of GLet vbe a vertex in G. Since Gis

connected, vis adjacent to at least 1 vertex. This means vhas at least 1

neighbor.

Step 3: Apply Pigeonhole Principle If we consider the neighbors of v,

by the Pigeonhole Principle, at least two of these neighbors must be connected

to vto form a cycle.

Step 4: Analyze the possible cycles If two neighbors of vare connected

to v, then we have a cycle of length 3. If more than two neighbors are connected

to v, then we will definitely have a cycle of length at most 3.

Therefore, Gcontains a cycle of length at most 3.

Question 21

Question

Let Gbe a connected graph with 12 vertices and 15 edges. Determine the

number of faces in the planar representation of G.

Solution

Let v,e, and fdenote the number of vertices, edges, and faces of a connected

planar graph, respectively. By Euler’s formula, we have v−e+f= 2 for any

connected planar graph.

Step 1: Start by substituting the given values into Euler’s formula.

12 −15 + f= 2

Step 2: Simplify the equation to find the number of faces.

f= 15 −12 + 2 = 5

So, the number of faces in the planar representation of Gis 5 .

Question 22

Question

Let Gbe a connected graph with 15 vertices and 23 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 make use of the

fact that if a connected graph has nvertices and at least nedges, then the graph

contains a cycle.

Step 1: Determine if Gis a tree. Since Gis connected and has 15 vertices

and 23 edges, Gcannot be a tree (a tree on 15 vertices would have 14 edges).

Step 2: Use the fact that Gcontains a cycle. Since Gis not a tree, it

contains a cycle. Let Cbe the shortest cycle in G.

Step 3: Show that Chas length at most 6. Suppose for the sake of contra-

diction that Chas length at least 7. Since Cis a cycle, it must contain at least

3 edges. Therefore, Cmust contain at least 7 edges, which is a contradiction

since Cis the shortest cycle in G. Thus, Chas length at most 6.

Therefore, we have shown that there exists a cycle of length at most 6 in the

graph G.

Question 23

Question

Let Gbe a connected graph with 10 vertices and 16 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 fact that

Gis a connected graph with 10 vertices and 16 edges.

Step 1: Use the handshake lemma to find the average degree of vertices in

G. According to the handshake lemma, the sum of the degrees of all vertices in

a graph is equal to twice the number of edges. Since Ghas 10 vertices and 16

edges, the sum of the degrees of all vertices is 2 ×16 = 32. Thus, the average

degree of vertices in Gis 32

10 = 3.2.

Step 2: Use the Pigeonhole Principle to find a vertex with degree at most

3. Assume, for the sake of contradiction, that all vertices in Ghave degree at

least 4. Since the average degree is 3.2, there must be at least one vertex with

degree at most 3. Let vbe such a vertex.

Step 3: Consider the neighbors of vertex v. Since vhas degree at most 3, it

has at most 3 neighboring vertices. If any pair of these neighbors are adjacent,

then we have found a cycle of length at most 4 (including v). Thus, assume

that the neighbors of vare not adjacent to each other.

Step 4: Consider the degrees of the neighbors of vertex v. Each neighbor

of vhas degree at least 4 since they are not adjacent to each other. This means

that each neighbor of vis connected to at least one more vertex besides v.

Step 5: Count the number of vertices connected to the neighbors of v. Since

each neighbor of vis connected to at least one more vertex besides v, there are

at least 3*1 + 3 = 6 vertices connected to the neighbors of v. However, these

vertices include vand its neighbors, which add up to at most 1 + 3 = 4 vertices.

Step 6: Utilize the Pigeonhole Principle to find a common neighbor. Since

there are at least 6 vertices connected to the neighbors of vbut only 4 distinct

vertices, at least 2 of the neighbors of vmust share a common neighbor, say u.

Then, the path v−ufollowed by uto one of v’s neighbors and then back to v

creates a cycle of length at most 4, completing the proof.

Therefore, the graph Gmust contain a cycle of length at most 4.

Question 24

Question

Let G= (V, E) be a graph with |V|= 10 vertices and |E|= 25 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 the

Pigeonhole Principle.

Step 1: Calculate the maximum number of edges in a graph without a cycle

of length 4.

Let Gbe a graph with nvertices and no cycle of length 4. The maximum number

of edges in such a graph can be found using Tur´an’s theorem. For a graph

without a 4-cycle, the maximum number of edges is given by 1−1

r−1·n2

where ris the length of the cycle we want to avoid. Substituting n= 10 and

r= 4, we get:

1−1

3·102

2=2

3·50 = 33

Step 2: Apply the Pigeonhole Principle.

Since the graph Ghas 25 edges, which is greater than 24 edges (the maximum

possible in a graph without a 4-cycle), by the Pigeonhole Principle, there must

be at least one 4-cycle (since 25 is more than 24, the theoretical maximum

without a 4-cycle).

Therefore, the graph Gcontains a cycle of length at least 4.

Question 25

Question

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

least 3. Prove that Gcontains a cycle of length at most 6.

Solution

Assume, for the sake of contradiction, that Gdoes not contain a cycle of length

at most 6.

Step 1: Let’s consider the longest path in G. Since Gis connected, this

path must contain all 10 vertices.

Step 2: Since the longest path contains all vertices, each vertex, except for

the endpoints, must have exactly 2 neighbors on the path. If any vertex had

more than 2 neighbors on the path, then a shorter cycle could be formed.

Step 3: The endpoints of the longest path can each connect to at most one

vertex on the path. Otherwise, a shorter cycle could be formed.

Step 4: Considering the degrees of the endpoints, they must each have

at least 3 neighbors in the graph, which means they must have at least one

neighbor not on the longest path.

Step 5: By introducing either of these neighbors into the longest path, a

cycle of length at most 6 would be formed. This is a contradiction.

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

6 must be false, and hence Gmust contain a cycle of length at most 6.

Question 26

Question

Let Gbe a connected simple graph with 10 vertices and 18 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 simple graph with nvertices and medges contains a cycle if m≥n.

Step 1: Calculate the minimum number of edges for a cycle of

length 4. For a cycle of length 4, we need at least 4 edges.

Step 2: Calculate the maximum number of edges for a cycle of

length 3. In a cycle of length 3, there are 3 vertices and 3 edges. However,

this cycle consists of only vertices and edges and does not contain any internal

vertices. The 3 vertices account for 3 edges.

Step 3: Calculate the maximum number of edges for a cycle of

length at least 4. To form a cycle of length 4, we need to add at least

one internal vertex. This internal vertex will add another edge to the cycle.

Therefore, in a cycle of length 4, there are 4 vertices and 5 edges in total.

Step 4: Use the fact that a connected simple graph with n vertices

and m edges contains a cycle if m ≥n. Given that Gis a connected simple

graph with 10 vertices and 18 edges, we have m= 18 and n= 10. To ensure

the presence of a cycle, we aim to compare these values with the minimum and

maximum values required for a cycle of length at least 4.

Step 5: Compare the number of edges in G with the number

required for a cycle of length at least 4. As 18 ≥10, Gcontains a cycle of

at least length 3. Since 18 <5 + 10 = 15, Gdoes not contain a cycle of length

4, but as 18 ≥10, Gdoes contain a cycle of length at least 4.

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

least 4.

Question 27

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 use the Pigeonhole

Principle.

Step 1: Assume for the sake of contradiction that Gdoes not contain a

cycle of length at most 4.

Step 2: Let vbe a vertex in Gwith the maximum degree. Since Gis

connected and has 10 vertices, the maximum degree of vis at most 9.

Step 3: Consider the neighbors of v. By the Pigeonhole Principle, vmust

have at least two neighbors that have a common neighbor with v(since vhas

at most 9 neighbors and each vertex can be adjacent to at most 4 other vertices

in a cycle of length 4).

Step 4: Let uand wbe two neighbors of vthat have a common neighbor

with v. We can form a cycle of length at most 4 by considering the vertices u,

v, the common neighbor of uand v, and w.

Step 5: This contradicts our assumption that Gdoes not contain a cycle of

length at most 4. Therefore, our initial assumption is false and Gmust contain

a cycle of length at most 4.

Question 28

Question

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

contain a cycle with length at most 4.

Solution

To prove that the graph Gmust contain a cycle with length at most 4, we will

use the Pigeonhole Principle.

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

vertices A tree with 12 vertices will have 11 edges. This is because in a tree

with nvertices, there are always n−1 edges.

Step 2: Calculate the number of edges beyond a tree in GSince

Ghas 20 edges, and a tree with 12 vertices can have a maximum of 11 edges,

there must be at least 20 −11 = 9 edges that form cycles in G.

Step 3: Identify the cycle length using the Pigeonhole Principle

Consider the 9 edges that form cycles in G. Since the maximum cycle length

that could exist is 12 (a cycle going through all vertices), the possible cycle

lengths are 3, 4, 5, ..., 12.

Step 4: Applying the Pigeonhole Principle Divide the 9 edges into

groups according to their cycle lengths. At least one group must contain more

than one edge by the Pigeonhole Principle.

Step 5: Finding the cycle of length at most 4 Since a cycle of length

3 contains 3 edges forming a triangle, and a cycle of length 4 is just a square,

we can conclude that there must exist a cycle with length at most 4 in G.

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

20 edges must contain a cycle with length at most 4.

Question 29

Question

Let Gbe a simple graph with 12 vertices and 20 edges. If every vertex in Ghas

degree at least 3, 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 a simple graph with 12 vertices and 20 edges, we know that the

total sum of the degrees of all vertices is twice the number of edges. This is the

Handshaking Lemma, which states that Pdeg(v)=2|E|.

So, in our case, 12 ·3≤Pdeg(v)=2·20 = 40.

Step 2: Count the number of edges in G.

Since every vertex in Ghas degree at least 3, the minimum number of edges

that Gcan have is obtained by assuming that each vertex has degree exactly 3.

In this case, the sum of degrees would be 12 ·3 = 36, which would require 18

edges.

But we are given that Gactually contains 20 edges. This means that there

must be some vertices with degree greater than 3 in order to have a total of 20

edges.

Step 3: Consider the vertices with degree greater than 3.

Let vbe a vertex in Gwith degree greater than 3. Since vhas at least 4

neighbors, there must be a neighbor wof vsuch that wis connected to some

other neighbor of v(other than vitself).

This creates a cycle of length at least 4: v−w−x−v, where xis the other

neighbor of vconnected to w.

Step 4: Contradiction.

We have shown that if Gdoes not contain a cycle of length at least 4,

then there must be some vertices with degree greater than 3 which leads to the

creation of such a cycle. This contradicts our initial assumption.

Therefore, our assumption must be false, and we conclude that Gmust

contain a cycle of length at least 4.

Question 30

Question

Let Gbe a connected graph with 10 vertices and 20 edges. Prove that Gis not

a tree.

Solution

Step 1: Recall that a tree is a connected graph with no cycles.

Step 2: Note that a tree with nvertices has exactly n−1 edges.

Step 3: Since Ghas 10 vertices and 20 edges, it has more edges than a tree

with 10 vertices would have.

Step 4: Therefore, we can conclude that Gis not a tree, as it violates the

property of having one less edge than the number of vertices.

Step 5: Hence, the graph Gis not a tree.

Question 31

Question

Let Gbe a connected graph with nvertices and medges, where n≥2 and

m≥n. Prove that if Ghas a cycle, then Ghas at least m−n+ 1 edges.

Solution

To prove that if Ghas a cycle, then Ghas at least m−n+ 1 edges, we will use

the fact that any connected graph with nvertices has at least n−1 edges.

Step 1: Assume Ghas a cycle. Let Cbe a cycle in Gwith kedges. Since G

is connected, every vertex in the graph must be a part of the cycle C. Therefore,

Chas nvertices.

Step 2: Count the number of edges outside the cycle. Since Ghas medges

and Chas kedges, there are m−kedges in the graph that are not part of the

cycle C.

Step 3: Count the minimum number of edges needed to connect all vertices

in the cycle. To create a connected graph with nvertices (the vertices in the

cycle C), we need at least n−1 edges. These edges must be distinct from the

edges in the cycle C.

Step 4: Calculate the minimum number of edges in G. Therefore, the

minimum number of edges in Gis k+ (n−1) = n+k−1. Since m > n, we

have m≥n+ 1. Combining this with the previous step, we get m≥n+k−1.

Step 5: Conclude the proof. Since m≥n+k−1, it follows that m≥

m−n+ 1, which proves that if Ghas a cycle, then Ghas at least m−n+ 1

edges.

Question 32

Question

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

no cycles of length 3, then m≤n2

Solution

Suppose Gis a connected graph with nvertices and medges, and it has no

cycles of length 3.

Step 1: Counting the number of edges in each face Consider any face

fin the planar embedding of G. Each face is bounded by a cycle, and since G

has no cycles of length 3, each face has at least 4 edges bounding it (forming

a cycle of length 4 or more). Let fibe the number of edges in face i, where i

ranges from 1 to the total number of faces f. Then we have:

4f≤2m

Step 2: Counting the number of edges in the graph By Euler’s

formula, we have that for a connected planar graph with nvertices, medges,

and ffaces:

n−m+f= 2

Since Gis connected, we have f= 1, so the equation becomes:

n−m+ 1 = 2

m=n−1

Step 3: Combining the inequalities Substitute m=n−1 into 4f≤2m:

4≤2(n−1)

n≤5

Therefore, for a graph Gwith no cycles of length 3, the number of vertices

nmust be less than or equal to 5. Thus, the maximum number of edges in this

case will be:

m=n−1≤5−1=4

Therefore, m≤n2

4for a graph Gwith no cycles of length 3.

Question 33

Question

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

a tree.

Solution

To show that Gis not a tree, we will use the fact that a tree on nvertices has

n−1 edges.

Step 1: Find the number of edges in a tree on 10 vertices. A tree on n

vertices has n−1 edges. Therefore, a tree on 10 vertices should have 10 −1=9

edges.

Step 2: Determine if Ghas more than 9 edges. Given that Gis a connected

graph with 10 vertices and 16 edges, since 16 is greater than 9, Ghas more

edges than a tree on 10 vertices.

Step 3: Conclude that Gis not a tree. Since Ghas more edges than a tree

on the same vertices, Gcannot be a tree. Therefore, Gis not a tree.

Question 34

Question

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

a cycle with at least 4 vertices.

Solution

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

the following theorem: If a connected graph has more edges than vertices, then

it contains a cycle.

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

graph with 10 vertices. For a connected graph with nvertices, it must have at

least n−1 edges to ensure connectivity. Therefore, for 10 vertices, the minimum

number of edges required is 10 −1 = 9 edges.

Step 2: Given that the graph Ghas 15 edges, which is greater than the

minimum (9 edges) required for a connected graph with 10 vertices, we can

conclude that Gcontains a cycle.

Step 3: Determine the smallest possible cycle in G. Since Gis connected

with 10 vertices and 15 edges, it is possible that Gcontains a cycle with 3

vertices (a triangle). To exclude the possibility of a 3-vertex cycle, let’s assume

that all cycles in Ghave 3 vertices and calculate the maximum number of edges

in such cycles.

A cycle with 3 vertices has 3 edges. If all cycles in Ghave 3 vertices, then

the number of edges in these cycles would be a multiple of 3. However, 15 is

not a multiple of 3, which implies that there must be cycles with more than 3

vertices in G.

Step 4: Conclude that Gcontains a cycle with at least 4 vertices. Since G

contains cycles with more than 3 vertices, we can conclude that Gcontains a

cycle with at least 4 vertices, as required.

Question 35

Question

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

a cycle of length 4 or less.

Question 6

Question

Let Gbe a connected graph with 10 vertices, 15 edges, and exactly 3 vertices

of degree 5. Prove that Gcontains at least one cycle.

Solution

To prove that the graph Gcontains at least one cycle, we will use the fact that

connected graphs with nvertices and medges must contain at least one cycle

if m>n. We will first show that Gsatisfies this condition.

Step 1: Determine the total sum of degrees in G. Since Gis a graph with

10 vertices and 3 vertices of degree 5, we have:

Xdegrees = 2 ×number of edges = 2 ×15 = 30

Step 2: Find the sum of degrees of the remaining vertices. Let v1, v2, v3be

the vertices of degree 5 and v4, v5, ..., v10 be the remaining vertices. The sum of

the degrees of vertices v4to v10 is:

i=4

degree(vi) = 30 −3×5 = 15

Step 3: Determine the minimum possible degree of the remaining vertices.

Since a connected graph has at least one edge incident to each vertex, the

minimum degree of the remaining vertices is 1. Thus, the sum of the degrees of

the remaining vertices is at least 7 ×1 = 7.

Step 4: Sum of degrees is greater than or equal to 15 + 7 = 22. Therefore,

the sum of the degrees of all vertices in Gis at least 22, which means there are

at least 22 edges incident to the vertices in G.

Step 5: Since Ghas 15 edges, m > n condition is satisfied. There are 15

edges in Gand 10 vertices, so m= 15 > n = 10. Therefore, by the theorem

mentioned at the beginning, Gmust contain at least one cycle.

Hence, we have proven that graph Gcontains at least one cycle.

Question 7

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.