Introducing Graphs

Videos

Introducing Graphs (6:45)
Degrees of Nodes (7:25)
Walks, Paths, and Cycles (6:29)
Special Graphs (4:19)

Reading

Warmup

Problem 1

Let \(G\) be a complete graph with \(n\) nodes. Give a formula for the number of edges in \(G\) as a function of \(n\). You are not required to write a formal proof of your answer, but please explain your reasoning.

Problem 2

Let \(G\) be a bipartite graph with \(10\) nodes. What is the largest possible number of edges that \(G\) can contain? A formal proof is not required, but please explain your reasoning in describing why your answer is correct.

Note: You’ll need to check the definition of bipartite graph in the reading.

Problem 3

True or False:

There exists a graph with 5 nodes in which each edge has degree exactly equal to 3.
Every connected graph contains at least one cycle.
Every tree is connected.
Any regular graph of degree 2 is a tree.