How many walks are there of 6 steps… (a) On \(K_7\)? (b) On \(C_7\)?
How many paths of 3 edges are there… (a) In \(K_7\)? (b) In \(C_7\)?
Let \(G\) be a connected graph with at least two vertices. Prove that there is at least one vertex \(v\) in \(G\) that can be removed (along with all edges connected to \(v\)) while leaving the remaining graph connected.
Here’s one way we can prove this.
The distance \(d(u,v)\) between two vertices \(u,v\) in a graph \(G\) is the length of the shortest path between them (If there is no path, the distance is infinite).
Pick a vertex \(w\) in \(G\).
Explain why there is a vertex \(v\) in \(G\) which maximizes \(d(w, v)\).
Explain why for any vertex \(u \ne v\) in \(G\) there is a path from \(w\) to \(u\) that does not include \(v\).
Conclude that removing \(v\) from \(G\) leaves \(G\) connected.