Exercises for Question Type 1: Determining properties of a given simple graph

Question 1

A simple graph G has adjacency matrix 0110010110110110110100110 Determine the number of connected components and identify them.

[3]

Question 2

In a simple undirected graph G with 6 vertices and 9 edges, calculate the sum of degrees of all vertices and confirm the Handshaking Lemma.

[3]

Question 3

Decide whether the simple graph with vertices {V_{1}, V_{2}, V_{3}, V_{4}, V_{5}} and edges {V_{1}, V_{2}}, {V_{2}, V_{3}}, {V_{3}, V_{4}}, {V_{4}, V_{5}}, {V_{5}, V_{1}} is complete, connected, and contains any circuits. Justify your answers.

[6]

Question 4

Given the degree sequence (4, 3, 3, 3, 2, 1), determine if it is graphical, and if so, use the Havel-Hakimi algorithm to construct a corresponding simple graph.

[8]

Question 5

Given the simple graph G defined by the adjacency list : 1 : {2, 3} 2 : {1, 3, 4} 3 : {1, 2, 4} 4 : {2, 3, 5} 5 : {4} Determine whether G contains an Eulerian trail or circuit.

[4]

Question 6

Given the degree sequence (3, 3, 2, 2, 2, 2), determine whether there is a simple graph with this degree sequence and, if so, construct one.

[6]

Question 7

Consider an electrical circuit where nodes 1, 2, 3, 4 are junctions and resistors connect nodes (1, 2), (2, 3), (3, 4), (4, 1), and (2, 4) . Represent this circuit as a simple graph and find the degree of each vertex.

[4]

Question 8

Construct a simple graph with 7 vertices labeled P, Q, R, S, T, U, V such that deg (P) = 3, deg (Q) = 3, deg (R) = 2, deg (S) = 2, deg (T) = 2, deg (U) = 1, and deg (V) = 1 . Provide the edge set E .

[3]

Question 9

Given the simple graph G with vertex set V = {A, B, C, D} and edge set E = {{A, B}, {A, C}, {B, C}, {C, D}}, determine the degree of each vertex and list the vertices adjacent to C .

[3]

Question 10

Given a simple graph G with vertices 1 to 6 and edge set E = {{1, 2}, {2, 3}, {3, 1}, {4, 5}, {5, 6}, {6, 4}} . Is G connected? Find all connected components and determine if G contains any circuits.

[4]

Question 11

The following table represents the friendship strengths between five people A, B, C, D, and E . A friendship strength \geq 6 defines an edge in a simple graph representing their social network. A B C D E A - 7564 B 7 - 836 C 58 - 62 D 636 - 7 E 4627 -

Draw the corresponding simple graph and determine the degree of each vertex.

[4]

Question 12

Given the adjacency matrix 0101101001011010, list the adjacency list representation of the corresponding graph.

[2]

IB Mathematics Applications & Interpretation Question Type 1: Determining Properties of a Given Simple Graph Exercises