Quiz 2
Registry Synced

Graph Theory: Basic Definitions

186 words
1 min read

Reading compass

Now · 5.1 Basic Definitions

Graph Theory: Basic Definitions

5.1 Basic Definitions

A graph G=(V,E)G = (V, E) consists of:
  • VV = set of vertices (nodes)
  • EE = set of edges (pairs of vertices) Types:
  • Simple graph: No loops or multiple edges
  • Directed graph (digraph): Edges have direction
  • Weighted graph: Edges have weights

5.2 Degree and Handshaking Lemma

Degree deg⁡(v)\deg(v) = number of edges incident to vv.
∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|
Corollary: Every graph has an even number of odd-degree vertices.

5.3 Paths and Cycles

  • Walk: Sequence of vertices where consecutive vertices are adjacent
  • Path: Walk with no repeated vertices
  • Cycle: Path that starts and ends at same vertex
  • Connected: For every pair of vertices, there's a path between them
  • Component: Maximal connected subgraph

5.4 Special Graphs

GraphNotationProperties
Complete graphKnK_n(n2)\binom{n}{2} edges, every pair adjacent
CycleCnC_nnn vertices forming a single cycle
PathPnP_nnn vertices in a line
BipartiteKm,nK_{m,n}Two parts, all edges between parts
Complete bipartiteKm,nK_{m,n}All possible edges between parts
Join Discord PreviousGenerating FunctionsNextGraph Coloring & Planarity
Document outline

Keep your place and jump directly to a heading.

Table of Contents
System Normal // Awaiting Context

Intelligence Hub

Navigate the knowledge graph to generate context. The Hub adapts dynamically to surface backlinks, related notes, and metadata insights.

Open library →Launch Assessment Engine