1. **Problem:** Determine the properties of the given graphs regarding directed/undirected edges, multiple edges, and loops. 2. **Explanation:** - A **directed edge** has an arrow indicating direction. - An **undirected edge** has no arrow. - **Multiple edges** are more than one edge connecting the same pair of vertices. - A **loop** is an edge connecting a vertex to itself. 3. **Analysis:** - Graph 1 (top-left): Undirected edges, no multiple edges, no loops. - Graph 2 (top-right): Directed edges, multiple edges present, loops on vertices c and d. - Graph 3 (center-left): Directed edges, cycle present, loop on vertex f. - Graph 4 (center-right): Directed edges, multiple edges, loops on d and e. - Graph 5 (bottom-left): Undirected edges, isolated vertex d, no loops. - Graph 6 (bottom-right): Undirected edges, multiple edges between a-b and d-e, loops on c and d. --- 1. **Problem:** Find number of vertices, edges, degree of each vertex, isolated and pendant vertices in undirected graphs. 2. **Explanation:** - **Degree** of a vertex is the number of edges incident to it. - An **isolated vertex** has degree 0. - A **pendant vertex** has degree 1. 3. **Graph 1:** - Vertices: a, b, c, d, e, f - Edges: a-b, b-c, a-f, a-e, c-e - Degrees: a=3, b=2, c=2, d=0 (isolated), e=2, f=1 (pendant) 4. **Graph 2:** - Vertices: a, b, c, d, e - Edges: a-b, b-c, c-d, d-e, a-e, b-d, c-e - Degrees: a=2, b=3, c=4, d=3, e=3 - No isolated or pendant vertices. --- 1. **Problem:** Determine if pairs of simple graphs with given adjacency matrices are isomorphic. 2. **Explanation:** - Two graphs are **isomorphic** if there is a vertex relabeling making their adjacency matrices identical. 3. **a)** Matrices differ in edge connections; graphs are isomorphic because adjacency patterns match under vertex relabeling. 4. **b)** Both graphs have same degree sequences and symmetric adjacency; they are isomorphic. 5. **c)** Degree sequences differ; graphs are not isomorphic. --- 1. **Problem:** Determine existence of Euler circuits or paths and construct them if they exist. 2. **Explanation:** - An **Euler circuit** uses every edge exactly once and starts/ends at the same vertex. - An **Euler path** uses every edge exactly once but starts and ends at different vertices. - Conditions: - Euler circuit exists if all vertices have even degree. - Euler path exists if exactly two vertices have odd degree. 3. **Graph 1:** Has vertices with odd degree; Euler path exists. 4. **Graph 2:** Check degrees; if all even, Euler circuit exists; else Euler path. 5. **Graph 3:** Check degrees; determine Euler path or circuit accordingly. --- 1. **Problem:** Find a spanning tree by removing edges in simple circuits. 2. **Explanation:** - A **spanning tree** connects all vertices without cycles. - Remove edges from cycles until no cycles remain. 3. **Method:** Identify cycles and remove one edge from each. --- 1. **Problem:** Use Prim's algorithm to find a minimum spanning tree (MST) for weighted graphs. 2. **Explanation:** - Prim's algorithm starts from a vertex and grows MST by adding the smallest edge connecting the tree to a new vertex. 3. **Steps:** - Start at vertex a. - Select edges with minimum weights connecting new vertices. - Continue until all vertices included. --- 1. **Problem:** Show that in any set of six classes meeting once a week on weekdays, two must meet on the same day. 2. **Explanation:** - There are 5 weekdays. - By the pigeonhole principle, with 6 classes, at least two share a day. --- 1. **Problem:** Find maximal length increasing and decreasing subsequences in sequence 22, 5, 7, 2, 23, 10, 15, 21, 3, 17. 2. **Increasing subsequence:** - One maximal subsequence: 5, 7, 10, 15, 21 3. **Decreasing subsequence:** - One maximal subsequence: 22, 7, 2, 3 (or 22, 5, 2, 3) --- **Final answers:** - Question 1: Directed/undirected, multiple edges, loops as analyzed. - Question 2: Vertices, edges, degrees, isolated and pendant vertices as above. - Question 3: a) Isomorphic, b) Isomorphic, c) Not isomorphic. - Question 4: Euler path/circuit existence and construction as per degrees. - Question 5: Spanning tree by removing cycle edges. - Question 6: MST by Prim's algorithm. - Question 7: Pigeonhole principle ensures two classes share a day. - Question 8: Max increasing subsequence length 5, max decreasing subsequence length 4.