Graph Theory Basics

Welcome, everyone! Let's start our journey into the world of graph theory. So, what exactly is a graph?

Isn't it just a way to represent connections between things?

Exactly! A graph consists of two sets: vertices and edges. Vertices are often called nodes, and edges denote the connections between these nodes.

And what's the significance of these two sets?

The set of vertices cannot be empty, while the set of edges can be. This means you can have a graph without edges but always with nodes. Remember: V for Vertices and E for Edges! We'll use that as a memory aid: V&E.

So, graphs can exist without edges? That seems odd!

It does, but that's essential in graph theory as it allows flexibility in representation. Let’s summarize: Graphs are collections of vertices and edges, where V is the vertex set and E is the edge set.

Now, let’s dive deeper into types of graphs. Can anyone tell me the difference between directed and undirected graphs?

Directed graphs have arrows, right? Like showing one node leads to another.

Correct! In directed graphs, edges are ordered pairs, meaning the direction matters. If there's an edge from A to B, it's not the same as from B to A.

So, undirected graphs don’t have that direction?

Exactly! In undirected graphs, edges are treated as unordered pairs, meaning A-B is the same as B-A. Think of undirected graphs as 'friendship' connections.

What about simple graphs?

Great question! A simple graph has no self-loops and at most one edge between two nodes. Let’s keep that in mind: 'No self-loops, one edge' for simple graphs!

Next, we need to talk about adjacency. Who remembers what it means for two vertices to be adjacent?

It's when they're connected by an edge, right?

Exactly! If there’s an edge connecting two vertices, say A and B, then A and B are adjacent. Every edge connects two vertices.

What about the degree of a vertex? How does that work?

Great question! The degree of a vertex is simply the number of edges connected to it. If a vertex has a self-loop, that counts as 2 towards its degree!

So if a vertex has two edges plus a self-loop, its degree is 4?

Exactly right! Remember: Degree = edges connected + 2 for each self-loop.

Next up, let’s discuss the Handshaking Theorem. Who can tell me what it states?

Doesn’t it say something about the sum of the degrees of the vertices?

Absolutely! It states that the sum of the degrees of all vertices in an undirected graph is equal to twice the number of edges. Remember this: S=2E for Sum and Edges.

So if I sum up the degrees and get an even number, what does that mean?

Great connection! If it's even, it means we can conclude that the number of vertices with odd degrees is also even. This is known as Euler's theorem.

Finally, let’s look into some special types of graphs. What can you tell me about complete graphs?

A complete graph has every vertex connected to every other vertex with exactly one edge.

Exactly! So for n vertices, we denote this complete graph as K_n. Now, what is a bipartite graph?

That's when we can split the vertex set into two groups and connect every vertex in one group to every vertex in the other.

Correct! That’s a complete bipartite graph. But remember, it has to connect every vertex from one set to another—no edges within the same set!