1. **Problem:** Prove that a connected graph is Eulerian if and only if all its vertices have even degree. **Step 1:** Recall the definition: A graph is Eulerian if it contains a cycle that uses every edge exactly once. **Step 2:** \(\Rightarrow\) If a graph is Eulerian, every time the Eulerian circuit enters a vertex, it must leave it through a distinct edge. Hence edges are paired, implying each vertex has even degree. **Step 3:** \(\Leftarrow\) If every vertex has even degree in a connected graph, an Eulerian circuit exists according to Euler's theorem, because you can start at any vertex and traverse edges without getting stuck until all are used. 2. **Problem:** Are Graph 1 (pentagon cycle) and Graph 2 (5-point star) isomorphic? **Step 1:** Check number of vertices and edges: Both have 5 vertices. **Step 2:** Check vertex degrees: In Graph 1 each vertex has degree 2; in Graph 2, the central vertex has degree 4 and others have degree 2 or 3. **Step 3:** Since degree sequences differ, graphs are not isomorphic. 3. **Problem:** Construct adjacency matrix for a weighted directed graph. **Step 1:** Label vertices say \(v_1, v_2, \ldots, v_n\). **Step 2:** Construct an \(n \times n\) matrix where element \(a_{ij}\) equals the weight of the edge from vertex \(v_i\) to \(v_j\) if it exists, else 0. **Step 3:** Interpretation: matrix shows presence and weight of directed edges; nonzero elements represent connections and weights show the cost or capacity. 4. **Problem:** For given weighted graph with vertices A,B,C,E,F,G: (a) Find degree sequence. **Step 1:** Count edges for each vertex (treat undirected edges; count edges connected to vertex): - A connected to B(11),C(33),G(27),E(23),F(17) → degree 5 - B connected to A(11),E(43),F(25),C(13),G(15) → degree 5 - C connected to A(33),F(37),G(41),B(13),E(36) → degree 5 - E connected to B(43),G(45),F(14),A(23),C(36) → degree 5 - F connected to B(25),C(37),E(14),G(19),A(17) → degree 5 - G connected to A(27),C(41),E(45),F(19),B(15) → degree 5 Degree sequence: $$5,5,5,5,5,5$$ (b) Is graph Eulerian or Hamiltonian? **Step 1:** Eulerian requires all vertices have even degree, here all are 5 (odd) → Not Eulerian. **Step 2:** Hamiltonian means a cycle visiting all vertices exactly once. **Step 3:** Since this is a complete weighted graph with 6 vertices, Hamiltonian cycles exist. 5. **Problem:** Explain application of graph theory in network routing. **Example:** Use shortest path algorithms (like Dijkstra's) on a weighted graph where vertices represent routers and edges represent communication links with weights as latency. The algorithm finds the minimum latency route for data packets. Final answers: 1. Connected graph is Eulerian if and only if all vertices have even degree. 2. The pentagon and 5-point star graphs are not isomorphic. 3. Adjacency matrix lists weights of directed edges; zeros for no edges. 4. (a) Degree sequence is $$5,5,5,5,5,5$$. (b) Graph is not Eulerian but is Hamiltonian. 5. Graph theory is fundamental in optimizing network routing via shortest path algorithms.