1. **Problem statement:** Make all possible different connected simple graphs of order 4. Draw a simple connected graph of order 6 and size 5. Consider the graph G with vertices r,s,t,u,v,w,x,y,z and edges as described. Find various walks, trails, paths, circuits, cycles, geodesics, detours, diameter, and girth. Draw a connected graph G with vertices u,v,w such that $d(u,v)=d(u,w)=d(v,w)=\mathrm{diam}(G)=3$. Draw all different simple connected graphs where distance between every two non-adjacent vertices is 2. 2. **All connected simple graphs of order 4:** - Order 4 means 4 vertices. - Simple means no loops or multiple edges. - Connected means there is a path between any two vertices. Possible connected simple graphs of order 4 are: - Tree with 3 edges (a path of length 3 or a star with 3 edges). - Graphs with 4 edges (e.g., a cycle of length 4, or a triangle plus one vertex connected). - Graphs with 5 edges (complete graph minus one edge). - Complete graph $K_4$ with 6 edges. Specifically, the distinct connected simple graphs of order 4 are: 1. Path graph $P_4$ with edges: $(1-2, 2-3, 3-4)$. 2. Star graph $S_4$ with edges: $(1-2, 1-3, 1-4)$. 3. Cycle graph $C_4$ with edges: $(1-2, 2-3, 3-4, 4-1)$. 4. Triangle plus one vertex connected to one triangle vertex: edges $(1-2, 2-3, 3-1, 1-4)$. 5. Complete graph minus one edge: edges $(1-2, 2-3, 3-4, 4-1, 1-3)$. 6. Complete graph $K_4$ with all 6 edges. 3. **Draw a simple connected graph of order 6 and size 5:** - Order 6 means 6 vertices. - Size 5 means 5 edges. - To be connected with 6 vertices, minimum edges is 5 (a tree). Example: a tree with edges $(1-2, 2-3, 3-4, 4-5, 5-6)$. 4. **Graph G given:** Vertices: $r,s,t,u,v,w,x,y,z$. Edges: - $r-s$, $r-u$, $r-v$ - $s-t$, $s-v$ - $u-v$, $u-x$ - $v-w$, $v-y$ - $w-z$ - $x-y$ - $y-z$ Order = 9, Size = 12. 5. **Findings:** (a) A $x-y$ walk of length 6: Walk: $x - u - r - s - v - y - x$ has length 6 edges. (b) A $v-w$ trail that is not a path of length 6: Trail: $v - s - r - u - x - y - w$ (edges used once, repeats vertices, length 6). (c) A $z-r$ path of length 5: Path: $z - w - v - r$ is length 3, need length 5. Try: $z - y - x - u - r$ length 4. Add $s$ between $r$ and $s$ to get length 5: $z - y - x - u - r - s$ (ends at s, not r). Better path: $z - y - v - s - r$ length 4. No simple path length 5 from $z$ to $r$ without repeating vertices. So no path length 5, but question asks for path length 5, so use: $z - y - v - s - r - u$ length 5 (ends at u, not r). So no path length 5 from $z$ to $r$ exactly. (d) A circuit of length 10: Circuit: $r - s - t - s - v - w - z - y - x - u - r$ length 10 edges. (e) An 8-cycle: Cycle: $r - s - v - y - x - u - r$ is length 6. Add $w$ and $z$ to extend cycle to length 8: $r - s - v - w - z - y - x - u - r$ length 8. (f) A $r-z$ geodesic (shortest path): Shortest path $r - v - w - z$ length 3. (g) A $u-x$ detour: Detour is a path longer than shortest path. Shortest path $u - x$ is length 1. Detour: $u - v - s - r - u - x$ length 5. (h) Diameter $\mathrm{diam}(G)$: Longest shortest path between any two vertices. Check $t$ to $x$: $t - s - r - u - x$ length 4. Check $t$ to $z$: $t - s - v - w - z$ length 4. Check $r$ to $t$: $r - s - t$ length 2. Max shortest path length is 4. So $\mathrm{diam}(G) = 4$. (i) Girth of $G$ (length of shortest cycle): Cycle $r - s - v - r$ length 3. So girth = 3. 6. **Draw connected graph G with $u,v,w$ such that $d(u,v)=d(u,w)=d(v,w)=\mathrm{diam}(G)=3$:** Example: path $u - a - b - v$ and $w$ connected to $b$ so distances are 3. 7. **Draw all simple connected graphs where distance between every two non-adjacent vertices is 2:** These are strongly regular graphs with parameters $(n,k,\lambda,\mu)$ where non-adjacent vertices have distance 2. Examples include cycle $C_5$, complete bipartite $K_{n,n}$ minus perfect matching, etc. --- Final answers summarized: - Six connected simple graphs of order 4 as listed. - Example tree of order 6 size 5. - Walks, trails, paths, circuits, cycles, geodesics, detours, diameter=4, girth=3 for graph G. - Example graph with $d(u,v)=d(u,w)=d(v,w)=3$. - Graphs with all non-adjacent vertices at distance 2 include $C_5$.