All questions of Graph Theory for Civil Engineering (CE) Exam

The correct answer is:

c) G3 = (V, E3) where E3 = {(u, v)|(u, v) ∈ E and u ≠ v}

Explanation:

The strongly connected components of a directed graph G are subsets of vertices where there is a directed path from any vertex to any other vertex within the subset.

In G1, every edge in E1 is reversed compared to G. This means that if there is a strongly connected component in G, there will be a strongly connected component in G1, but the edges within that component will be reversed. Thus, G1 does not have the same strongly connected components as G.

In G2, the edges in E2 are a subset of the edges in E. This means that if there is a strongly connected component in G, there will be a strongly connected component in G2, but it is possible that there are additional edges in G that do not belong to any strongly connected component in G2. Thus, G2 does not have the same strongly connected components as G.

In G3, the edges in E3 are the same as the edges in E, but with the restriction that the source and destination vertices are not the same. This means that if there is a strongly connected component in G, there will be a strongly connected component in G3 with the same edges. Thus, G3 has the same strongly connected components as G.

Definition of Degree

The degree of a vertex in a graph refers to the number of edges that are incident with that particular vertex. In other words, it represents the number of connections or links that a vertex has with other vertices in the graph.

Explanation of the Answer

The correct answer is option 'A', which states that the degree of any vertex in a graph is the number of edges incident with that vertex. This means that the degree of a vertex is determined by counting the number of edges that are directly connected to that vertex.

Understanding the Degree of a Vertex

To understand this concept better, let's consider a simple example. Suppose we have a graph consisting of four vertices: A, B, C, and D. The edges in the graph are represented by the lines connecting the vertices.

If we focus on vertex A, we can see that it is connected to three edges: one edge connects A to B, another edge connects A to C, and the third edge connects A to D. Therefore, the degree of vertex A is 3.

Similarly, if we analyze vertex B, we can see that it is connected to two edges: one edge connects B to A and the other edge connects B to C. Thus, the degree of vertex B is 2.

We can follow the same procedure to determine the degree of vertices C and D. Vertex C is connected to three edges (C-A, C-B, and C-D), and vertex D is connected to two edges (D-A and D-C). Hence, the degrees of vertices C and D are 3 and 2, respectively.

Conclusion

In summary, the degree of any vertex in a graph is the number of edges incident with that vertex. It represents the number of connections or links that a vertex has with other vertices in the graph. By counting the number of edges directly connected to a vertex, we can determine its degree.

A) The diagonal entries of A^2 are not necessarily the degrees of the vertices of the graph. The diagonal entries of A^2 represent the number of length-2 paths between each pair of vertices in the graph. The degrees of the vertices are represented by the diagonal entries of A.

b) If the graph is connected, then all entries of A^(n-1) + A^(n-2) + ... + A + I (where I is the identity matrix) are positive. This is known as the matrix-tree theorem, and it states that the sum of these matrices (up to A^(n-1)) gives the Laplacian matrix of the graph, and the determinant of the Laplacian matrix is equal to the number of spanning trees in the graph. Therefore, if the graph is connected, the determinant of the Laplacian matrix is non-zero, which means none of the entries of A^(n-1) + A^(n-2) + ... + A + I can be zero.

c) If the sum of all the elements of A is at most 2(n - 1), it does not necessarily mean that the graph is acyclic. The sum of all the elements of A represents the total number of edges in the graph. If this sum is at most 2(n - 1), it means that the graph has at most 2(n-1) edges, which is the maximum number of edges in a tree. However, the graph could still have cycles if it is not a tree.

d) If there is at least a 1 in each of A, then it means that each vertex is connected to at least one other vertex in the graph. This does not necessarily imply any specific property of the graph, as it could still have cycles and be a connected graph.

Explanation:

Understanding the problem:
- We are given a graph 'H' which is the complement graph of an n-dimensional cube.
- It is mentioned that there are y * 210 edges in graph 'H' when n = 11.

Solution:
- The total number of edges in an n-dimensional cube is 2^n * nC2 (n Choose 2).
- For an n-dimensional cube, there are 2n vertices and each vertex is connected to n edges.
- Therefore, the total number of edges in an n-dimensional cube is 2^n * nC2.
- Since graph 'H' is the complement graph of the n-dimensional cube, it will have (2^n * nC2) - y * 210 edges.
- Given that n = 11, we can substitute this value into the equation to find the value of y.
- Therefore, y * 210 = 2^11 * 11C2 - 2^11 * 11C2 = 2036.
- Hence, the value of y is 2036.

True Statements:

(II) Every wheel graph is Hamiltonian:
A wheel graph is formed by connecting a single central vertex to all the vertices of a cycle graph. In a wheel graph, there is a Hamiltonian cycle that visits every vertex exactly once. The cycle can start from any vertex in the outer cycle and then move to the central vertex before returning to the starting vertex. Therefore, every wheel graph is Hamiltonian.

False Statements:

(I) Every complete graph is Hamiltonian:
A complete graph is a graph in which every pair of distinct vertices is connected by an edge. While it is true that a complete graph with three or more vertices is Hamiltonian, this statement does not hold for complete graphs with one or two vertices. In a complete graph with one vertex, there is no Hamiltonian cycle as there are no other vertices to visit. In a complete graph with two vertices, there is only one edge and no Hamiltonian cycle can be formed. Therefore, not every complete graph is Hamiltonian.

(III) Every complete bipartite graph is Hamiltonian:
A complete bipartite graph is a graph in which the vertices can be partitioned into two sets such that every vertex in one set is connected to every vertex in the other set. In a complete bipartite graph, there is no Hamiltonian cycle. This can be proven by considering the number of vertices and edges in the graph. The number of vertices in a complete bipartite graph is the product of the sizes of the two sets, which can be large. On the other hand, the number of edges is the product of the sizes of the two sets, which can be much smaller. Therefore, the number of edges is significantly less than the number of vertices, making it impossible to form a Hamiltonian cycle. Therefore, not every complete bipartite graph is Hamiltonian.

Conclusion:
The only true statement is that every wheel graph is Hamiltonian. The other two statements are false, as not every complete graph or complete bipartite graph is Hamiltonian.

The given information describes an undirected graph with specific degrees of vertices. We need to determine the number of vertices with degree 1.

Understanding the Graph
An undirected graph consists of vertices (nodes) and edges (connections between vertices). In this case, the graph has certain degree values for each vertex, representing the number of edges connected to that vertex.

The given graph has:
- 2 vertices with degree 4
- 1 vertex with degree 3
- 2 vertices with degree 2

Degree of a Vertex
The degree of a vertex is the count of edges connected to it. In an undirected graph, the degree is the same for both incoming and outgoing edges.

Simple Path
A simple path is a path in a graph that does not contain any repeated vertices. In other words, it is a path that visits each vertex only once.

Analysis
Let's analyze the information given and try to determine the number of vertices with degree 1.

Vertices with Degree 4
Since there are two vertices with degree 4, let's label them as A and B. The only simple path between these two vertices can be AB or BA.

Vertex with Degree 3
There is one vertex with degree 3, let's label it as C.

Vertices with Degree 2
Since there are two vertices with degree 2, let's label them as D and E.

Connecting the Vertices
Based on the given information, we can connect the vertices as follows:
- A is connected to B (degree 4)
- B is connected to C (degree 3)
- C is connected to D (degree 2)
- D is connected to E (degree 2)

Calculating the Remaining Degrees
To determine the number of vertices with degree 1, we need to calculate the remaining degrees.

- Degree of A: 4 (already determined)
- Degree of B: 4 (already determined)
- Degree of C: 3 (already determined)
- Degree of D: 2 (already determined)
- Degree of E: 2 (already determined)

To find the remaining degrees, we can use the handshaking lemma, which states that the sum of degrees of all vertices in an undirected graph is twice the number of edges.

We have the following vertices and degrees:
- A: 4
- B: 4
- C: 3
- D: 2
- E: 2

The total sum of degrees is 4 + 4 + 3 + 2 + 2 = 15.

Using the handshaking lemma, we can calculate the number of edges:
2 * number of edges = sum of degrees
2 * number of edges = 15
number of edges = 15 / 2
number of edges = 7.5

Since the graph is described as having a simple path between each pair of vertices, the number of edges should be a whole number. Therefore, there must be 7 edges in the graph.

Calculating the Degree 1 Vertices
To calculate the number of vertices with degree 1, we can subtract the degrees of the given vertices from the total sum of degrees in the graph.

Total sum

Answer:

A graph is a mathematical representation of a set of objects, called vertices, along with a set of connections between these objects, called edges. In this context, a vertex represents a point or a node, and an edge represents a connection or a relationship between two vertices.

A graph G is said to be k-regular if the degree of each vertex in G is equal to k. The degree of a vertex is defined as the number of edges incident to that vertex. So, if for every vertex v in G, the degree of v is k, then G is called a k-regular graph.

Let's analyze the given options:

a) K graph: The term "K graph" is not a standard term in graph theory. It is unclear what it refers to, so it cannot be the correct answer.

b) K-regular graph: As mentioned earlier, a graph G is called a k-regular graph if the degree of every vertex in G is equal to k. This is exactly the condition given in the question. Therefore, the correct answer is option B.

c) Empty graph: An empty graph is a graph with no vertices and no edges. Since the given graph G has vertices (as mentioned in the question), it cannot be an empty graph. Hence, option C is incorrect.

d) All of above: This option includes all the previous options (a, b, and c). Since option C is incorrect (as explained above), option D cannot be the correct answer.

In conclusion, the correct answer is option B, which states that if the degree of every vertex v in the graph G is equal to k, then G is called a k-regular graph.

For the complete bipartite graph $K_{m,n}$ to have a Hamilton circuit, we need every vertex to have degree at least 2.

The degree of each vertex in the left part of the graph is $n$, since it is connected to every vertex in the right part. Similarly, the degree of each vertex in the right part is $m$.

Therefore, we need $m \geq 2$ and $n \geq 2$ for every vertex to have degree at least 2.

If $m=1$ or $n=1$, then one of the parts of the graph only has one vertex, and thus it cannot have a Hamilton circuit.

So the answer is: $m \geq 2$ and $n \geq 2$.

To calculate the value of resistance (R) of each coil in a star connected network, we can use the following formula:

R = V / (I * √3 * PF)

Where:
R = resistance of each coil
V = supply voltage (230 volts)
I = current (given by P / (V * PF))
√3 = square root of 3
PF = power factor (0.8)

Let's calculate the current first:

P = power consumed by the network (20 kW)
V = supply voltage (230 volts)
PF = power factor (0.8)

I = P / (V * PF)
I = 20,000 / (230 * 0.8)
I ≈ 108.7 amps

Now, let's calculate the resistance:

R = V / (I * √3 * PF)
R = 230 / (108.7 * √3 * 0.8)
R ≈ 1.692 ohms

Therefore, the value of resistance for each coil in the star connected network is approximately 1.692 ohms.

Explanation:

A bipartite graph is a graph whose vertices can be divided into two independent sets, such that every edge connects a vertex in one set to a vertex in the other set.

To find the maximum number of edges in a bipartite graph on 12 vertices, we need to consider the case where the two sets of vertices have equal size.

Let the two sets of vertices be A and B, each with 6 vertices. The maximum number of edges that can be formed between vertices in A and B is when every vertex in A is connected to every vertex in B. This gives us a total of 6 * 6 = 36 edges.

Answer: 36

The maximum degree of any vertex in a simple graph with n vertices is n - 1.

Explanation:
A simple graph is a graph that does not contain any loops (edges that connect a vertex to itself) or multiple edges (more than one edge between the same pair of vertices). In other words, each edge in a simple graph connects two distinct vertices.

In a simple graph with n vertices, each vertex can be connected to at most n - 1 other vertices. This is because a vertex cannot be connected to itself, so it can have at most n - 1 neighboring vertices.

To understand why the maximum degree of any vertex is n - 1, let's consider the worst-case scenario. In this scenario, each vertex in the graph is connected to every other vertex, creating a complete graph.

Key Points:
- A complete graph is a graph in which every pair of distinct vertices is connected by an edge.
- In a complete graph with n vertices, each vertex is connected to every other vertex.
- Therefore, the degree of each vertex in a complete graph is n - 1.

Example:
Let's consider a simple graph with 5 vertices. The maximum degree of any vertex in this graph is 4 (n - 1).

(2)------(3)
| |
| |
(1)------(4)
|
(5)

In the above example, each vertex is connected to at most 4 other vertices. Therefore, the maximum degree of any vertex is 4.

Conclusion:
In a simple graph with n vertices, the maximum degree of any vertex is n - 1. This is because each vertex can be connected to at most n - 1 other vertices.