Reading: Read sections 12.1, 12.2, 12.3
Exercises:
How many subgraphs does a cycle of length 4 have? Assume the vertices are labelled \(a, b, c, d\). We consider the subgraph with two vertices \(a, b\) and a single edge \(ab\) to be different from the subgraph with two vertices \(b, c\) and a single edge \(bc\).
Suggestion: Count the number of subgraphs with 0 vertices, then the number of subgraphs with 1 vertex, and so on.
We’ll proceed by number of vertices. There are…
1 subgraph (the empty graph) with no vertices,
\(\binom 4 1\) subgraphs with 1 vertex (just choose 1 vertex),
\(\binom 4 2 + \binom 4 1\) subgraphs with 2 vertices (either choose two vertices and no edges, or choose an edge that comes with 2 vertices for free),
\(\binom 4 3 + \binom 4 1 \binom 2 1 + 4\) subgraphs with 3 vertices (either choose 3 vertices with no edges, or choose an edge that comes with 2 vertices and an extra vertex, or choose one connected subpath),
\(2^4\) subgraphs with 4 vertices (all vertices have to be chosen, so just pick which edges are in/out from the 4 there are).
In total, we get \(1 + 4 + (6 + 4) + (4 + 4(2) + 4) + (16) = 47\) subgraphs.
Draw a connected graph on 6 vertices with degrees 3,2,2,1,1,1.
Draw a disconnected graph on 6 vertices with degrees 3,2,2,1,1,1.
The graph will have no cycles.
The graph will have at least one cycle.
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).
What is the largest distance between any two vertices in the path graph of \(n\) edges \(P_n\)?
What is the largest distance between any two vertices in the cycle graph of \(n\) edges \(C_n\)?
What is the largest distance between any two vertices in the complete graph of \(n\) vertices \(K_n\)?
The largest distance is end-to-end, which is \(n\).
The largest distance is antipodal, which depends on parity of \(n\). If \(n\) is even, the furthest endpoint from any point is \(n/2\) away, if \(n\) is odd there are two distant endpoints each of which \((n-1)/2\) away.
Every two vertices are connected by an edge so the largest distance is \(1\).
Does \(K_5\) contain a closed Eulerian walk? Explain.
Does \(K_6\) contain a closed Eulerian walk? Explain.
Yes, every vertex is even degree.
No, every vertex is odd degree; there is not even an open Eulerian walk as there are more than two odd degree vertices.