1. **Problem 1: Given graph G with vertices and edges, find vertex set, edge set, degree of vertices, order, and size of G.** Step 1: Identify the vertex set $V$ from the problem statement: $$V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8\}$$ Step 2: Identify the edge set $E$ from the given connections: $$E = \{(v_1,v_2), (v_1,v_4), (v_2,v_3), (v_2,v_4), (v_3,v_5), (v_4,v_5), (v_5,v_6), (v_6,v_7), (v_7,v_8)\}$$ Step 3: Calculate the degree of each vertex (number of edges incident to vertex): - $\deg(v_1) = 2$ (edges to $v_2, v_4$) - $\deg(v_2) = 3$ (edges to $v_1, v_3, v_4$) - $\deg(v_3) = 2$ (edges to $v_2, v_5$) - $\deg(v_4) = 3$ (edges to $v_1, v_2, v_5$) - $\deg(v_5) = 3$ (edges to $v_3, v_4, v_6$) - $\deg(v_6) = 2$ (edges to $v_5, v_7$) - $\deg(v_7) = 2$ (edges to $v_6, v_8$) - $\deg(v_8) = 1$ (edge to $v_7$) Step 4: Find order of the graph (number of vertices): $$\text{order} = |V| = 8$$ Step 5: Find size of the graph (number of edges): $$\text{size} = |E| = 9$$ --- 2. **Problem 2: John attends a party of 10, each person knows some others, find how many people John (person 1) knows.** Step 1: Given degrees of people 2 to 9: 7,3,4,5,5,4,3,2,1 respectively. There seems a typo repeating person 9 twice; assuming degrees list:2(7),3(3),4(4),5(5),6(5),7(4),8(3),9(2),10(1). Step 2: Sum degrees of known persons: $$7 + 3 + 4 + 5 + 5 + 4 + 3 + 2 + 1 = 34$$ Step 3: Using Handshaking lemma for undirected graph: $$\sum_{i=1}^{10} \deg(v_i) = 2|E|$$ Step 4: Let John's degree be $x$. Then: $$x + 34 = 2|E|$$ Step 5: $x$ must satisfy $0 \leq x \leq 9$ (he can know from 0 up to 9 others). Also, in the context degrees should make $x+34$ even. Step 6: Since $34$ is even, $x$ must be even so total sum is even. Possible even values for $x = 0,2,4,6,8$. Step 7: Without more constraints, $x$ is not uniquely determined, but must be an even number between 0 and 8. --- 3. **Problem 3: For flow chart vertices A to H with given edges, find the length of shortest execution path and give one path of length 15.** Step 1: Given edges: - $A \to B$ - $B \to C, B \to D, B \to E$ - $C \to E$ - $D \to E$ - $F \to F$ - $G \to G, G \to H$ Step 2: Find shortest path from $A$ to $H$: Note: $A \to B$, the paths forward from $B$ don't reach $G$ or $H$ except through $G$? $H$ is only reachable from $G$, and $G$ only from itself. No given edge connects from $B,C,D,E$ to $F$ or $G$, so path from $A$ to $H$ is impossible by given edges. Step 3: Possibly the graph description missed edges that connect $E$ to $F$ or $G$. Assuming $E \to G$ is missing to make $H$ reachable, the shortest path would be: $$A \to B \to E \to G \to H$$ Length is number of vertices in sequence: 5 steps. Step 4: Possible execution sequence with 15 steps (vertices) that includes loops: $$A \to B \to D \to E \to G \to G \to G \to G \to G \to G \to G \to G \to G \to G \to H$$ (Repeatedly loop at vertex $G$ 10 times.) Step 5: Thus shortest sequence length is 5 and an execution sequence with 15 steps is as above. --- **Final answers:** **Problem 1:** - Vertex set $V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8\}$ - Edge set $E = \{(v_1,v_2), (v_1,v_4), (v_2,v_3), (v_2,v_4), (v_3,v_5), (v_4,v_5), (v_5,v_6), (v_6,v_7), (v_7,v_8)\}$ - Degrees: - $\deg(v_1)=2, \deg(v_2)=3, \deg(v_3)=2, \deg(v_4)=3,$ - $\deg(v_5)=3, \deg(v_6)=2, \deg(v_7)=2, \deg(v_8)=1$ - Order $=8$ - Size $=9$ **Problem 2:** John (person 1) knows an even number of people $x$ such that $x \in \{0,2,4,6,8\}$ based on Handshaking lemma; exact number not uniquely determined. **Problem 3:** - Shortest execution sequence length is 5. - One possible execution sequence with 15 vertices (steps): $$A \to B \to D \to E \to G \to G \to G \to G \to G \to G \to G \to G \to G \to G \to H$$