-
Notifications
You must be signed in to change notification settings - Fork 0
/
Wikipedia Glossary of Graph Theory Terms.txt
1188 lines (1188 loc) · 215 KB
/
Wikipedia Glossary of Graph Theory Terms.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
Introduction (Wikipedia Glossary of Graph Theory Terms)|"
<p>This deck has taken definitions outlined in <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">Wikipedia's Glossary of graph theory terms</a> and put them into a form which can be easily learnt/revised using <a href=""https://apps.ankiweb.net/"">Anki</a> a cross platform app specifically designed for long term knowledge retention.</p>
<h2>Notes</h2>
<p>Please note the modifications which have been made & where you can find updates.</p>
<ol align=""left"">
<li>The front of every card has ""(Wikipedia Glossary of Graph Theory Terms)"" appended to the end so that if you have any other words in your collection, the Wikipedia definition will still be added when importing it.</li>
<li>Any updates or corrections to the deck will be available at <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards</a> so do return periodically to check if you have the latest version.</li>
</ol>
<p>Feel free to share the deck and give the repository a star so more people are likely to see this work and can get the most out of it.</p>
<h2>License</h2>
<p>Unless otherwise specified, everything in this deck is covered by the following licence:</p>
<p>This deck uses material from the Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a>, which is released under the <a href=""https://creativecommons.org/licenses/by-sa/3.0/"">Creative Commons Attribution-Share-Alike License 3.0</a>.</p>
<p>To see this work in full go to <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms</a></p>
"
Square brackets [ ] (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary""><span class=""texhtml""><i>G</i>[<i>S</i>]</span> is the <a href=""#induced""><span title=""See entry on this page at § induced"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">induced subgraph</span></a> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> for vertex subset <span class=""texhtml mvar"" style=""font-style:italic;"">S</span>.</dd>
"
Prime symbol ' (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Prime_(symbol)"" title=""Prime (symbol)"">prime symbol</a> is often used to modify notation for graph invariants so that it applies to the <a href=""https://en.wikipedia.org/wiki/Line_graph"" title=""Line graph"">line graph</a> instead of the given graph. For instance, <span class=""texhtml""><i>α</i>(<i>G</i>)</span> is the independence number of a graph; <span class=""texhtml""><i>α</i>′(<i>G</i>)</span> is the matching number of the graph, which equals the independence number of its line graph. Similarly, <span class=""texhtml""><i>χ</i>(<i>G</i>)</span> is the chromatic number of a graph; <span class=""texhtml""><i>χ</i> ′(<i>G</i>)</span> is the chromatic index of the graph, which equals the chromatic number of its line graph.</dd>
"
achromatic (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Achromatic_number"" class=""mw-redirect"" title=""Achromatic number"">achromatic number</a> of a graph is the maximum number of colors in a complete coloring.<sup id=""cite_ref-1"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-1"">[1]</a></sup></dd>
"
acyclic (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A graph is acyclic if it has no cycles. An undirected acyclic graph is the same thing as a <a href=""https://en.wikipedia.org/wiki/Tree_(graph_theory)"" title=""Tree (graph theory)"">forest</a>. <a href=""https://en.wikipedia.org/wiki/Directed_acyclic_graph"" title=""Directed acyclic graph"">Directed acyclic graphs</a> are less often called acyclic directed graphs.<sup id=""cite_ref-clrs_2-0"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-clrs-2"">[2]</a></sup></dd>
<dd class=""glossary"">2.  An <a href=""https://en.wikipedia.org/wiki/Acyclic_coloring"" title=""Acyclic coloring"">acyclic coloring</a> of an undirected graph is a proper coloring in which every two color classes induce a forest.<sup id=""cite_ref-3"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-3"">[3]</a></sup></dd>
"
adjacency matrix (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Adjacency_matrix"" title=""Adjacency matrix"">adjacency matrix</a> of a graph is a matrix whose rows and columns are both indexed by vertices of the graph, with a one in the cell for row <span class=""texhtml mvar"" style=""font-style:italic;"">i</span> and column <span class=""texhtml mvar"" style=""font-style:italic;"">j</span> when vertices <span class=""texhtml mvar"" style=""font-style:italic;"">i</span> and <span class=""texhtml mvar"" style=""font-style:italic;"">j</span> are adjacent, and a zero otherwise.<sup id=""cite_ref-4"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-4"">[4]</a></sup></dd>
"
adjacent (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The relation between two vertices that are both endpoints of the same edge.<sup id=""cite_ref-clrs_2-1"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-clrs-2"">[2]</a></sup></dd>
"
<i>α</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">For a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, <span class=""texhtml""><i>α</i>(<i>G</i>)</span> (using the Greek letter alpha) is its independence number (see <a href=""#independent""><span title=""See entry on this page at § independent"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">independent</span></a>), and <span class=""texhtml""><i>α</i>′(<i>G</i>)</span> is its matching number (see <a href=""#matching""><span title=""See entry on this page at § matching"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">matching</span></a>).</dd>
"
alternating (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">In a graph with a matching, an alternating path is a path whose edges alternate between matched and unmatched edges. An alternating cycle is, similarly, a cycle whose edges alternate between matched and unmatched edges. An augmenting path is an alternating path that starts and ends at unsaturated vertices. A larger matching can be found as the <a href=""https://en.wikipedia.org/wiki/Symmetric_difference"" title=""Symmetric difference"">symmetric difference</a> of the matching and the augmenting path; a matching is maximum if and only if it has no augmenting path.</dd>
"
antichain (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">In a <a href=""https://en.wikipedia.org/wiki/Directed_acyclic_graph"" title=""Directed acyclic graph"">directed acyclic graph</a>, a subset <span class=""texhtml mvar"" style=""font-style:italic;"">S</span> of vertices that are pairwise incomparable, i.e., for any <span class=""mwe-math-element""><span class=""mwe-math-mathml-inline mwe-math-mathml-a11y"" style=""display: none;""><math xmlns=""http://www.w3.org/1998/Math/MathML"" alttext=""{\displaystyle x\leq y}"">
<semantics>
<mrow class=""MJX-TeXAtom-ORD"">
<mstyle displaystyle=""true"" scriptlevel=""0"">
<mi>x</mi>
<mo>≤<!-- ≤ --></mo>
<mi>y</mi>
</mstyle>
</mrow>
<annotation encoding=""application/x-tex"">{\displaystyle x\leq y}</annotation>
</semantics>
</math></span><img src=""https://wikimedia.org/api/rest_v1/media/math/render/svg/c07a0bc023490be1c08e6c33a9cdc93bec908224"" class=""mwe-math-fallback-image-inline"" aria-hidden=""true"" style=""vertical-align: -0.671ex; width:5.584ex; height:2.343ex;"" alt=""x\leq y""/></span> in <span class=""texhtml mvar"" style=""font-style:italic;"">S</span>, there is no directed path from <span class=""texhtml mvar"" style=""font-style:italic;"">x</span> to <span class=""texhtml mvar"" style=""font-style:italic;"">y</span> or from <span class=""texhtml mvar"" style=""font-style:italic;"">y</span> to <span class=""texhtml mvar"" style=""font-style:italic;"">x</span>. Inspired by the notion of <a href=""https://en.wikipedia.org/wiki/Antichain"" title=""Antichain"">antichains</a> in <a href=""https://en.wikipedia.org/wiki/Partially_ordered_set"" title=""Partially ordered set"">partially ordered sets</a>.</dd>
"
anti-edge (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Synonym for <i>non-edge</i>, a pair of non-adjacent vertices.</dd>
"
anti-triangle (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A three-vertex independent set, the complement of a triangle.</dd>
"
apex (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  An <a href=""https://en.wikipedia.org/wiki/Apex_graph"" title=""Apex graph"">apex graph</a> is a graph in which one vertex can be removed, leaving a planar subgraph. The removed vertex is called the apex. A <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-apex graph is a graph that can be made planar by the removal of <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> vertices.</dd>
<dd class=""glossary"">2.  Synonym for <a href=""https://en.wikipedia.org/wiki/Universal_vertex"" title=""Universal vertex"">universal vertex</a>, a vertex adjacent to all other vertices.</dd>
"
arborescence (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Synonym for a rooted and directed tree; see <a href=""#tree""><span title=""See entry on this page at § tree"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">tree</span></a>.</dd>
"
arc (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#edge""><span title=""See entry on this page at § edge"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">edge</span></a>.</dd>
"
arrow (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""https://en.wikipedia.org/wiki/Ordered_pair"" title=""Ordered pair"">ordered pair</a> of <a href=""#vertex""><span title=""See entry on this page at § vertex"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">vertices</span></a>, such as an <a href=""#edge""><span title=""See entry on this page at § edge"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">edge</span></a> in a <a href=""#directed_graph""><span title=""See entry on this page at § directed graph"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">directed graph</span></a>. An arrow <span class=""texhtml"">(<i>x</i>, <i>y</i>)</span> has a <a href=""#tail""><span title=""See entry on this page at § tail"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">tail</span></a> <span class=""texhtml""><i>x</i></span>, a <a href=""#head""><span title=""See entry on this page at § head"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">head</span></a> <span class=""texhtml""><i>y</i></span>, and a <a href=""#direction""><span title=""See entry on this page at § direction"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">direction</span></a> <span class=""texhtml"">from <i>x</i> to <i>y</i></span>; <span class=""texhtml""><i>y</i></span> is said to be the <a href=""#direct_successor""><span title=""See entry on this page at § direct successor"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">direct successor</span></a> to <span class=""texhtml""><i>x</i></span> and <span class=""texhtml""><i>x</i></span> the <a href=""#direct_predecessor""><span title=""See entry on this page at § direct predecessor"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">direct predecessor</span></a> to <span class=""texhtml""><i>y</i></span>. The arrow <span class=""texhtml"">(<i>y</i>, <i>x</i>)</span> is the <a href=""#inverted_arrow""><span title=""See entry on this page at § inverted arrow"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">inverted arrow</span></a> of the arrow <span class=""texhtml"">(<i>x</i>, <i>y</i>)</span>.</dd>
"
"<a href=""https://en.wikipedia.org/wiki/Articulation_point"" class=""mw-redirect"" title=""Articulation point"">articulation point</a> (Wikipedia Glossary of Graph Theory Terms)"|"
<dd class=""glossary"">A <a href=""#vertex""><span title=""See entry on this page at § vertex"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">vertex</span></a> in a <a href=""#connected_graph""><span title=""See entry on this page at § connected graph"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">connected graph</span></a> whose removal would <a href=""#disconnect""><span title=""See entry on this page at § disconnect"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">disconnect</span></a> the graph.</dd>
"
-ary (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/K-ary_tree"" class=""mw-redirect"" title=""K-ary tree""><span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-ary tree</a> is a rooted tree in which every internal vertex has no more than <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> children. A 1-ary tree is just a path. A 2-ary tree is also called a <a href=""https://en.wikipedia.org/wiki/Binary_tree"" title=""Binary tree"">binary tree</a>, although that term more properly refers to 2-ary trees in which the children of each node are distinguished as being left or right children (with at most one of each type). A <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-ary tree is said to be complete if every internal vertex has exactly <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> children.</dd>
"
augmenting (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A special type of alternating path; see <a href=""#alternating""><span title=""See entry on this page at § alternating"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">alternating</span></a>.</dd>
"
automorphism (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Graph_automorphism"" title=""Graph automorphism"">graph automorphism</a> is a symmetry of a graph, an isomorphism from the graph to itself.</dd>
"
bag (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">One of the sets of vertices in a <a href=""#tree_decomposition""><span title=""See entry on this page at § tree decomposition"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">tree decomposition</span></a>.</dd>
"
balanced (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A bipartite or multipartite graph is balanced if each two subsets of its vertex partition have sizes within one of each other.</dd>
"
bandwidth (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Graph_bandwidth"" title=""Graph bandwidth"">bandwidth</a> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the minimum, over all orderings of vertices of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, of the length of the longest edge (the number of steps in the ordering between its two endpoints). It is also one less than the size of the maximum clique in a proper interval completion of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, chosen to minimize the clique size.</dd>
"
biclique (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Synonym for <a href=""https://en.wikipedia.org/wiki/Complete_bipartite_graph"" title=""Complete bipartite graph"">complete bipartite graph</a> or complete bipartite subgraph; see <a href=""#complete""><span title=""See entry on this page at § complete"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">complete</span></a>.</dd>
"
biconnected (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Usually a synonym for <a href=""https://en.wikipedia.org/wiki/K-vertex-connected_graph"" title=""K-vertex-connected graph""><span class=""texhtml"">2</span>-vertex-connected</a>, but sometimes includes <i>K</i><sub>2</sub> though it is not 2-connected. See <a href=""#connected""><span title=""See entry on this page at § connected"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">connected</span></a>; for <a href=""https://en.wikipedia.org/wiki/Biconnected_component"" title=""Biconnected component"">biconnected components</a>, see <a href=""#component""><span title=""See entry on this page at § component"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">component</span></a>.</dd>
"
binding number (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The smallest possible ratio of the number of neighbors of a proper subset of vertices to the size of the subset.<sup id=""cite_ref-5"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-5"">[5]</a></sup></dd>
"
bipartite (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Bipartite_graph"" title=""Bipartite graph"">bipartite graph</a> is a graph whose vertices can be divided into two disjoint sets such that the vertices in one set are not connected to each other, but may be connected to vertices in the other set. Put another way, a bipartite graph is a graph with no odd cycles; equivalently, it is a graph that may be properly colored with two colors. Bipartite graphs are often written <span class=""texhtml""><i>G</i> = (<i>U</i>,<i>V</i>,<i>E</i>)</span> where <span class=""texhtml mvar"" style=""font-style:italic;"">U</span> and <span class=""texhtml mvar"" style=""font-style:italic;"">V</span> are the subsets of vertices of each color. However, unless the graph is connected, it may not have a unique 2-coloring.</dd>
"
biregular (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Biregular_graph"" title=""Biregular graph"">biregular graph</a> is a <a href=""#bipartite""><span title=""See entry on this page at § bipartite"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">bipartite</span></a> graph in which there are only two different vertex degrees, one for each set of the vertex bipartition.</dd>
"
block (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A block of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is a maximal subgraph which is either an isolated vertex, a bridge edge, or a 2-connected subgraph. If a block is 2-connected, every pair of vertices in it belong to a common cycle. Every edge of a graph belongs in exactly one block.</dd>
<dd class=""glossary"">2.  The block graph of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is another graph whose vertices are the blocks of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, with an edge connecting two vertices when the corresponding blocks share an articulation point; that is, it is the intersection graph of the blocks of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>. The block graph of any graph is a <a href=""#forest""><span title=""See entry on this page at § forest"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">forest</span></a>.</dd>
<dd class=""glossary"">3.  The block-cut (or block-cutpoint) graph of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> has as vertices the blocks and the articulation points separating them and its edges connect blocks to the articulation points within those blocks. The block-cut graph is a <a href=""#forest""><span title=""See entry on this page at § forest"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">forest</span></a> and if <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is connected it is a tree, called the block-cut tree of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>.</dd>
<dd class=""glossary"">4.  A <a href=""https://en.wikipedia.org/wiki/Block_graph"" title=""Block graph"">block graph</a> (also called a clique tree if connected, and sometimes erroneously called a Husimi tree) is a graph all of whose blocks are complete graphs. A <a href=""#forest""><span title=""See entry on this page at § forest"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">forest</span></a> is a block graph; so in particular the block graph of any graph is a block graph, and every block graph may be constructed as the block graph of a graph.</dd>
"
bond (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""#minimal""><span title=""See entry on this page at § minimal"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">minimal</span></a> <a href=""#cut-set""><span title=""See entry on this page at § cut-set"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">cut-set</span></a>: a set of edges whose removal disconnects the graph, for which no proper subset has the same property.</dd>
"
book (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/Book_(graph_theory)"" title=""Book (graph theory)"">book</a>, book graph, or triangular book is a complete tripartite graph <span class=""texhtml""><i>K</i><sub>1,1,<i>n</i></sub></span>; a collection of <span class=""texhtml mvar"" style=""font-style:italic;"">n</span> triangles joined at a shared edge.</dd>
<dd class=""glossary"">2.  Another type of graph, also called a book, or a quadrilateral book, is a collection of <span class=""texhtml"">4</span>-cycles joined at a shared edge; the Cartesian product of a star with an edge.</dd>
<dd class=""glossary"">3.  A <a href=""https://en.wikipedia.org/wiki/Book_embedding"" title=""Book embedding"">book embedding</a> is an embedding of a graph onto a topological book, a space formed by joining a collection of half-planes along a shared line. Usually, the vertices of the embedding are required to be on the line, which is called the spine of the embedding, and the edges of the embedding are required to lie within a single half-plane, one of the pages of the book.</dd>
"
bramble (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Bramble_(graph_theory)"" title=""Bramble (graph theory)"">bramble</a> is a collection of mutually touching connected subgraphs, where two subgraphs touch if they share a vertex or each includes one endpoint of an edge. The order of a bramble is the smallest size of a set of vertices that has a nonempty intersection with all of the subgraphs. The treewidth of a graph is the maximum order of any of its brambles.</dd>
"
branch-decomposition (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Branch-decomposition"" title=""Branch-decomposition"">branch-decomposition</a> of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is a hierarchical clustering of the edges of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, represented by an unrooted binary tree with its leaves labeled by the edges of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>. The width of a branch-decomposition is the maximum, over edges <span class=""texhtml mvar"" style=""font-style:italic;"">e</span> of this binary tree, of the number of shared vertices between the subgraphs determined by the edges of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> in the two subtrees separated by <span class=""texhtml mvar"" style=""font-style:italic;"">e</span>. The branchwidth of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the minimum width of any branch-decomposition of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>.</dd>
"
branchwidth (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#branch-decomposition""><span title=""See entry on this page at § branch-decomposition"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">branch-decomposition</span></a>.</dd>
"
bridge (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/Bridge_(graph_theory)"" title=""Bridge (graph theory)"">bridge</a>, isthmus, or cut edge is an edge whose removal would disconnect the graph. A bridgeless graph is one that has no bridges; equivalently, a 2-edge-connected graph.</dd>
<dd class=""glossary"">2.  Especially in the context of <a href=""https://en.wikipedia.org/wiki/Planarity_testing"" title=""Planarity testing"">planarity testing</a>, a bridge of a cycle is a maximal subgraph that is disjoint from the cycle and in which each two edges belong to a path that is internally disjoint from the cycle. A chord is a one-edge bridge. A <a href=""https://en.wikipedia.org/wiki/Peripheral_cycle"" title=""Peripheral cycle"">peripheral cycle</a> is a cycle with at most one bridge; it must be a face in any planar embedding of its graph.</dd>
<dd class=""glossary"">3.  A bridge of a cycle can also mean a path that connects two vertices of a cycle but is shorter than either of the paths in the cycle connecting the same two vertices. A <a href=""https://en.wikipedia.org/wiki/Bridged_graph"" class=""mw-redirect"" title=""Bridged graph"">bridged graph</a> is a graph in which every cycle of four or more vertices has a bridge.</dd>
"
bridgeless (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Bridgeless_graph"" class=""mw-redirect"" title=""Bridgeless graph"">bridgeless graph</a> is a graph that has no bridge edges; that is, a <a href=""https://en.wikipedia.org/wiki/K-edge-connected_graph"" title=""K-edge-connected graph"">2-edge-connected graph</a>.</dd>
"
butterfly (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  The <a href=""https://en.wikipedia.org/wiki/Butterfly_graph"" title=""Butterfly graph"">butterfly graph</a> has five vertices and six edges; it is formed by two triangles that share a vertex.</dd>
<dd class=""glossary"">2.  The butterfly network is a graph used as a network architecture in distributed computing, closely related to the <a href=""https://en.wikipedia.org/wiki/Cube-connected_cycles"" title=""Cube-connected cycles"">cube-connected cycles</a>.</dd>
"
<i>C</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary""><span class=""texhtml""><i>C</i><sub><i>n</i></sub></span> is an <span class=""texhtml mvar"" style=""font-style:italic;"">n</span>-vertex <a href=""https://en.wikipedia.org/wiki/Cycle_graph"" title=""Cycle graph"">cycle graph</a>; see <a href=""#cycle""><span title=""See entry on this page at § cycle"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">cycle</span></a>.</dd>
"
cactus (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Cactus_graph"" title=""Cactus graph"">cactus graph</a>, cactus tree, cactus, or Husimi tree is a connected graph in which each edge belongs to at most one cycle. Its blocks are cycles or single edges. If, in addition, each vertex belongs to at most two blocks, then it is called a Christmas cactus.</dd>
"
cage (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Cage_(graph_theory)"" title=""Cage (graph theory)"">cage</a> is a regular graph with the smallest possible order for its girth.</dd>
"
canonical (Wikipedia Glossary of Graph Theory Terms)|"
<p>Looks like this term doesn't have a definition yet.</p>
<p>Maybe consider making a contribution to this <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">project</a> or even better improve the original Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a> by making a contribution and <a href=""https://twitter.com/darigovresearch"">let us know</a>!</p>
"
canonization (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Canonical_form"" title=""Canonical form"">canonical form</a> of a graph is an invariant such that two graphs have equal invariants if and only if they are isomorphic. Canonical forms may also be called canonical invariants or complete invariants, and are sometimes defined only for the graphs within a particular family of graphs. <a href=""https://en.wikipedia.org/wiki/Graph_canonization"" title=""Graph canonization"">Graph canonization</a> is the process of computing a canonical form.</dd>
"
card (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A graph formed from a given graph by deleting one vertex, especially in the context of the <a href=""https://en.wikipedia.org/wiki/Reconstruction_conjecture"" title=""Reconstruction conjecture"">reconstruction conjecture</a>. See also <a href=""#deck""><span title=""See entry on this page at § deck"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">deck</span></a>, the multiset of all cards of a graph.</dd>
"
carving width (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Carving width is a notion of graph width analogous to branchwidth, but using hierarchical clusterings of vertices instead of hierarchical clusterings of edges.</dd>
"
caterpillar (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Caterpillar_tree"" title=""Caterpillar tree"">caterpillar tree</a> or caterpillar is a tree in which the internal nodes induce a path.</dd>
"
center (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Graph_center"" title=""Graph center"">center</a> of a graph is the set of vertices of minimum <a href=""#eccentricity""><span title=""See entry on this page at § eccentricity"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">eccentricity</span></a>.</dd>
"
chain (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  Synonym for <a href=""#walk""><span title=""See entry on this page at § walk"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">walk</span></a>.</dd>
<dd class=""glossary"">2.  When applying methods from <a href=""https://en.wikipedia.org/wiki/Algebraic_topology"" title=""Algebraic topology"">algebraic topology</a> to graphs, an element of a <a href=""https://en.wikipedia.org/wiki/Chain_complex"" title=""Chain complex"">chain complex</a>, namely a set of vertices or a set of edges.</dd>
"
Cheeger constant (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#expansion""><span title=""See entry on this page at § expansion"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">expansion</span></a>.</dd>
"
cherry (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A cherry is a path on three vertices.<sup id=""cite_ref-6"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-6"">[6]</a></sup></dd>
"
<i>χ</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary""><span class=""texhtml""><i>χ</i>(<i>G</i>)</span> (using the Greek letter chi) is the chromatic number of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> and <span class=""texhtml""><i>χ</i> ′(<i>G</i>)</span> is its chromatic index; see <a href=""#chromatic""><span title=""See entry on this page at § chromatic"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">chromatic</span></a> and <a href=""#coloring""><span title=""See entry on this page at § coloring"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">coloring</span></a>.</dd>
"
child (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">In a rooted tree, a child of a vertex <span class=""texhtml mvar"" style=""font-style:italic;"">v</span> is a neighbor of <span class=""texhtml mvar"" style=""font-style:italic;"">v</span> along an outgoing edge, one that is directed away from the root.</dd>
"
chord (Wikipedia Glossary of Graph Theory Terms)|"
<p>Looks like this term doesn't have a definition yet.</p>
<p>Maybe consider making a contribution to this <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">project</a> or even better improve the original Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a> by making a contribution and <a href=""https://twitter.com/darigovresearch"">let us know</a>!</p>
"
chordal (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A chord of a cycle is an edge that does not belong to the cycle, for which both endpoints belong to the cycle.</dd>
<dd class=""glossary"">2.  A <a href=""https://en.wikipedia.org/wiki/Chordal_graph"" title=""Chordal graph"">chordal graph</a> is a graph in which every cycle of four or more vertices has a chord, so the only induced cycles are triangles.</dd>
<dd class=""glossary"">3.  A <a href=""https://en.wikipedia.org/wiki/Strongly_chordal_graph"" title=""Strongly chordal graph"">strongly chordal graph</a> is a chordal graph in which every cycle of length six or more has an odd chord.</dd>
<dd class=""glossary"">4.  A <a href=""https://en.wikipedia.org/wiki/Chordal_bipartite_graph"" title=""Chordal bipartite graph"">chordal bipartite graph</a> is not chordal (unless it is a forest); it is a bipartite graph in which every cycle of six or more vertices has a chord, so the only induced cycles are 4-cycles.</dd>
<dd class=""glossary"">5.  A <a href=""https://en.wikipedia.org/wiki/Chord_(geometry)"" title=""Chord (geometry)"">chord of a circle</a> is a line segment connecting two points on the circle; the <a href=""https://en.wikipedia.org/wiki/Intersection_graph"" title=""Intersection graph"">intersection graph</a> of a collection of chords is called a <a href=""https://en.wikipedia.org/wiki/Circle_graph"" title=""Circle graph"">circle graph</a>.</dd>
"
chromatic (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Having to do with coloring; see <a href=""#color""><span title=""See entry on this page at § color"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">color</span></a>. Chromatic graph theory is the theory of graph coloring. The <a href=""https://en.wikipedia.org/wiki/Chromatic_number"" class=""mw-redirect"" title=""Chromatic number"">chromatic number</a> <span class=""texhtml""><i>χ</i>(<i>G</i>)</span> is the minimum number of colors needed in a proper coloring of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>. <span class=""texhtml""><i>χ</i> ′(<i>G</i>)</span> is the <a href=""https://en.wikipedia.org/wiki/Chromatic_index"" class=""mw-redirect"" title=""Chromatic index"">chromatic index</a> of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, the minimum number of colors needed in a proper <a href=""https://en.wikipedia.org/wiki/Edge_coloring"" title=""Edge coloring"">edge coloring</a> of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>.</dd>
"
choosable (Wikipedia Glossary of Graph Theory Terms)|"
<p>Looks like this term doesn't have a definition yet.</p>
<p>Maybe consider making a contribution to this <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">project</a> or even better improve the original Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a> by making a contribution and <a href=""https://twitter.com/darigovresearch"">let us know</a>!</p>
"
choosability (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A graph is <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-choosable if it has a <a href=""https://en.wikipedia.org/wiki/List_coloring"" title=""List coloring"">list coloring</a> whenever each vertex has a list of <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> available colors. The choosability of the graph is the smallest <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> for which it is <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-choosable.</dd>
"
circle (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Circle_graph"" title=""Circle graph"">circle graph</a> is the <a href=""https://en.wikipedia.org/wiki/Intersection_graph"" title=""Intersection graph"">intersection graph</a> of chords of a circle.</dd>
"
circuit (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A circuit may refer to a closed trail or an element of the <a href=""https://en.wikipedia.org/wiki/Cycle_space"" title=""Cycle space"">cycle space</a> (an Eulerian spanning subgraph). The <a href=""https://en.wikipedia.org/wiki/Circuit_rank"" title=""Circuit rank"">circuit rank</a> of a graph is the dimension of its cycle space.</dd>
"
circumference (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Circumference_(graph_theory)"" class=""mw-redirect"" title=""Circumference (graph theory)"">circumference</a> of a graph is the length of its longest simple cycle. The graph is Hamiltonian if and only if its circumference equals its order.</dd>
"
class (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/Class_(set_theory)"" title=""Class (set theory)"">class</a> of graphs or family of graphs is a (usually infinite) collection of graphs, often defined as the graphs having some specific property. The word ""class"" is used rather than ""set"" because, unless special restrictions are made (such as restricting the vertices to be drawn from a particular set, and defining edges to be sets of two vertices) classes of graphs are usually not sets when formalized using set theory.</dd>
<dd class=""glossary"">2.  A color class of a colored graph is the set of vertices or edges having one particular color.</dd>
<dd class=""glossary"">3.  In the context of <a href=""https://en.wikipedia.org/wiki/Vizing%27s_theorem"" title=""Vizing's theorem"">Vizing's theorem</a>, on edge coloring simple graphs, a graph is said to be of class one if its chromatic index equals its maximum degree, and class two if its chromatic index equals one plus the degree. According to Vizing's theorem, all simple graphs are either of class one or class two.</dd>
"
claw (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Claw_(graph_theory)"" class=""mw-redirect"" title=""Claw (graph theory)"">claw</a> is a tree with one internal vertex and three leaves, or equivalently the complete bipartite graph <span class=""texhtml""><i>K</i><sub>1,3</sub></span>. A <a href=""https://en.wikipedia.org/wiki/Claw-free_graph"" title=""Claw-free graph"">claw-free graph</a> is a graph that does not have an induced subgraph that is a claw.</dd>
"
clique (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Clique_(graph_theory)"" title=""Clique (graph theory)"">clique</a> is a set of mutually adjacent vertices (or the complete subgraph induced by that set). Sometimes a clique is defined as a maximal set of mutually adjacent vertices (or maximal complete subgraph), one that is not part of any larger such set (or subgraph). A <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-clique is a clique of order <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>. The <a href=""https://en.wikipedia.org/wiki/Clique_number"" class=""mw-redirect"" title=""Clique number"">clique number</a> <span class=""texhtml""><i>κ</i>(<i>G</i>)</span> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the order of its largest clique. A <a href=""https://en.wikipedia.org/wiki/Clique_graph"" title=""Clique graph"">clique graph</a> is an <a href=""https://en.wikipedia.org/wiki/Intersection_graph"" title=""Intersection graph"">intersection graph</a> of maximal cliques. See also <a href=""#biclique""><span title=""See entry on this page at § biclique"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">biclique</span></a>, a complete bipartite subgraph.</dd>
"
clique tree (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A synonym for a <a href=""#block_graph""><span title=""See entry on this page at § block graph"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">block graph</span></a>.</dd>
"
clique-width (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Clique-width"" title=""Clique-width"">clique-width</a> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the minimum number of distinct labels needed to construct <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> by operations that create a labeled vertex, form the disjoint union of two labeled graphs, add an edge connecting all pairs of vertices with given labels, or relabel all vertices with a given label. The graphs of clique-width at most <span class=""texhtml"">2</span> are exactly the <a href=""https://en.wikipedia.org/wiki/Cograph"" title=""Cograph"">cographs</a>.</dd>
"
closed (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A closed neighborhood is one that includes its central vertex; see <a href=""#neighbourhood""><span title=""See entry on this page at § neighbourhood"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">neighbourhood</span></a>.</dd>
<dd class=""glossary"">2.  A closed walk is one that starts and ends at the same vertex; see <a href=""#walk""><span title=""See entry on this page at § walk"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">walk</span></a>.</dd>
<dd class=""glossary"">3.  A graph is transitively closed if it equals its own transitive closure; see <a href=""#transitive""><span title=""See entry on this page at § transitive"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">transitive</span></a>.</dd>
<dd class=""glossary"">4.  A graph property is closed under some operation on graphs if, whenever the argument or arguments to the operation have the property, then so does the result. For instance, hereditary properties are closed under induced subgraphs; monotone properties are closed under subgraphs; and minor-closed properties are closed under minors.</dd>
"
closure (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  For the transitive closure of a directed graph, see <a href=""#transitive""><span title=""See entry on this page at § transitive"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">transitive</span></a>.</dd>
<dd class=""glossary"">2.  A closure of a directed graph is a set of vertices that have no outgoing edges to vertices outside the closure. For instance, a sink is a one-vertex closure. The <a href=""https://en.wikipedia.org/wiki/Closure_problem"" title=""Closure problem"">closure problem</a> is the problem of finding a closure of minimum or maximum weight.</dd>
"
co- (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">This prefix has various meanings usually involving <a href=""https://en.wikipedia.org/wiki/Complement_graph"" title=""Complement graph"">complement graphs</a>. For instance, a <a href=""https://en.wikipedia.org/wiki/Cograph"" title=""Cograph"">cograph</a> is a graph produced by operations that include complementation; a <a href=""https://en.wikipedia.org/wiki/Cocoloring"" title=""Cocoloring"">cocoloring</a> is a coloring in which each vertex induces either an independent set (as in proper coloring) or a clique (as in a coloring of the complement).</dd>
"
color (Wikipedia Glossary of Graph Theory Terms)|"
<p>Looks like this term doesn't have a definition yet.</p>
<p>Maybe consider making a contribution to this <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">project</a> or even better improve the original Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a> by making a contribution and <a href=""https://twitter.com/darigovresearch"">let us know</a>!</p>
"
coloring (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/Graph_coloring"" title=""Graph coloring"">graph coloring</a> is a labeling of the vertices of a graph by elements from a given set of colors, or equivalently a partition of the vertices into subsets, called ""color classes"", each of which is associated with one of the colors.</dd>
<dd class=""glossary"">2.  Some authors use ""coloring"", without qualification, to mean a proper coloring, one that assigns different colors to the endpoints of each edge. In graph coloring, the goal is to find a proper coloring that uses as few colors as possible; for instance, <a href=""https://en.wikipedia.org/wiki/Bipartite_graph"" title=""Bipartite graph"">bipartite graphs</a> are the graphs that have colorings with only two colors, and the <a href=""https://en.wikipedia.org/wiki/Four_color_theorem"" title=""Four color theorem"">four color theorem</a> states that every <a href=""https://en.wikipedia.org/wiki/Planar_graph"" title=""Planar graph"">planar graph</a> can be colored with at most four colors. A graph is said to be <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-colored if it has been (properly) colored with <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> colors, and <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-colorable or <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-chromatic if this is possible.</dd>
<dd class=""glossary"">3.  Many variations of coloring have been studied, including <a href=""https://en.wikipedia.org/wiki/Edge_coloring"" title=""Edge coloring"">edge coloring</a> (coloring edges so that no two edges with the same endpoint share a color), <a href=""https://en.wikipedia.org/wiki/List_coloring"" title=""List coloring"">list coloring</a> (proper coloring with each vertex restricted to a subset of the available colors), <a href=""https://en.wikipedia.org/wiki/Acyclic_coloring"" title=""Acyclic coloring"">acyclic coloring</a> (every 2-colored subgraph is acyclic), co-coloring (every color class induces an independent set or a clique), <a href=""https://en.wikipedia.org/wiki/Complete_coloring"" title=""Complete coloring"">complete coloring</a> (every two color classes share an edge), and <a href=""https://en.wikipedia.org/wiki/Total_coloring"" title=""Total coloring"">total coloring</a> (both edges and vertices are colored).</dd>
<dd class=""glossary"">4.  The coloring number of a graph is one plus the <a href=""https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)"" title=""Degeneracy (graph theory)"">degeneracy</a>. It is so called because applying a greedy coloring algorithm to a degeneracy ordering of the graph uses at most this many colors.</dd>
"
comparability (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An undirected graph is a <a href=""https://en.wikipedia.org/wiki/Comparability_graph"" title=""Comparability graph"">comparability graph</a> if its vertices are the elements of a <a href=""https://en.wikipedia.org/wiki/Partially_ordered_set"" title=""Partially ordered set"">partially ordered set</a> and two vertices are adjacent when they are comparable in the partial order. Equivalently, a comparability graph is a graph that has a transitive orientation. Many other classes of graphs can be defined as the comparability graphs of special types of partial order.</dd>
"
complement (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Complement_graph"" title=""Complement graph"">complement graph</a> <span class=""mwe-math-element""><span class=""mwe-math-mathml-inline mwe-math-mathml-a11y"" style=""display: none;""><math xmlns=""http://www.w3.org/1998/Math/MathML"" alttext=""{\displaystyle {\bar {G}}}"">
<semantics>
<mrow class=""MJX-TeXAtom-ORD"">
<mstyle displaystyle=""true"" scriptlevel=""0"">
<mrow class=""MJX-TeXAtom-ORD"">
<mrow class=""MJX-TeXAtom-ORD"">
<mover>
<mi>G</mi>
<mo stretchy=""false"">¯<!-- ¯ --></mo>
</mover>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding=""application/x-tex"">{\displaystyle {\bar {G}}}</annotation>
</semantics>
</math></span><img src=""https://wikimedia.org/api/rest_v1/media/math/render/svg/f5075b212a17b8fcd107d164d2d45ecac43591fd"" class=""mwe-math-fallback-image-inline"" aria-hidden=""true"" style=""vertical-align: -0.338ex; width:1.827ex; height:2.676ex;"" alt=""{\bar {G}}""/></span> of a simple graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is another graph on the same vertex set as <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, with an edge for each two vertices that are not adjacent in <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>.</dd>
"
complete (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/Complete_graph"" title=""Complete graph"">complete graph</a> is one in which every two vertices are adjacent: all edges that could exist are present. A complete graph with <span class=""texhtml mvar"" style=""font-style:italic;"">n</span> vertices is often denoted <span class=""texhtml""><i>K</i><sub><i>n</i></sub></span>. A <a href=""https://en.wikipedia.org/wiki/Complete_bipartite_graph"" title=""Complete bipartite graph"">complete bipartite graph</a> is one in which every two vertices on opposite sides of the partition of vertices are adjacent. A complete bipartite graph with <span class=""texhtml mvar"" style=""font-style:italic;"">a</span> vertices on one side of the partition and <span class=""texhtml mvar"" style=""font-style:italic;"">b</span> vertices on the other side is often denoted <span class=""texhtml""><i>K</i><sub><i>a</i>,<i>b</i></sub></span>. The same terminology and notation has also been extended to <a href=""https://en.wikipedia.org/wiki/Complete_multipartite_graph"" class=""mw-redirect"" title=""Complete multipartite graph"">complete multipartite graphs</a>, graphs in which the vertices are divided into more than two subsets and every pair of vertices in different subsets are adjacent; if the numbers of vertices in the subsets are <span class=""texhtml""><i>a</i>, <i>b</i>, <i>c</i>, ...</span> then this graph is denoted <span class=""texhtml""><i>K</i><sub><i>a</i>, <i>b</i>, <i>c</i>, ...</sub></span>.</dd>
<dd class=""glossary"">2.  A completion of a given graph is a supergraph that has some desired property. For instance, a <a href=""https://en.wikipedia.org/wiki/Chordal_completion"" title=""Chordal completion"">chordal completion</a> is a supergraph that is a chordal graph.</dd>
<dd class=""glossary"">3.  A complete matching is a synonym for a <a href=""https://en.wikipedia.org/wiki/Perfect_matching"" class=""mw-redirect"" title=""Perfect matching"">perfect matching</a>; see <a href=""#matching""><span title=""See entry on this page at § matching"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">matching</span></a>.</dd>
<dd class=""glossary"">4.  A <a href=""https://en.wikipedia.org/wiki/Complete_coloring"" title=""Complete coloring"">complete coloring</a> is a proper coloring in which each pairs of colors is used for the endpoints of at least one edge. Every coloring with a minimum number of colors is complete, but there may exist complete colorings with larger numbers of colors. The <a href=""https://en.wikipedia.org/wiki/Achromatic_number"" class=""mw-redirect"" title=""Achromatic number"">achromatic number</a> of a graph is the maximum number of colors in a complete coloring.</dd>
<dd class=""glossary"">5.  A complete invariant of a graph is a synonym for a canonical form, an invariant that has different values for non-isomorphic graphs.</dd>
"
component (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Connected_component_(graph_theory)"" class=""mw-redirect"" title=""Connected component (graph theory)"">connected component</a> of a graph is a maximal connected subgraph. The term is also used for maximal subgraphs or subsets of a graph's vertices that have some higher order of connectivity, including <a href=""https://en.wikipedia.org/wiki/Biconnected_component"" title=""Biconnected component"">biconnected components</a>, <a href=""https://en.wikipedia.org/wiki/Triconnected_component"" class=""mw-redirect"" title=""Triconnected component"">triconnected components</a>, and <a href=""https://en.wikipedia.org/wiki/Strongly_connected_component"" title=""Strongly connected component"">strongly connected components</a>.</dd>
"
condensation (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Condensation_(graph_theory)"" class=""mw-redirect"" title=""Condensation (graph theory)"">condensation</a> of a directed graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is a directed acyclic graph with one vertex for each strongly connected component of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, and an edge connecting pairs of components that contain the two endpoints of at least one edge in <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>.</dd>
"
cone (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A graph that contains a <a href=""https://en.wikipedia.org/wiki/Universal_vertex"" title=""Universal vertex"">universal vertex</a>.</dd>
"
connect (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Cause to be <a href=""#connected""><span title=""See entry on this page at § connected"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">connected</span></a>.</dd>
"
connected (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Connectivity_(graph_theory)"" title=""Connectivity (graph theory)"">connected graph</a> is one in which each pair of vertices forms the endpoints of a path. Higher forms of connectivity include strong connectivity in directed graphs (for each two vertices there are paths from one to the other in both directions), <a href=""https://en.wikipedia.org/wiki/K-vertex-connected_graph"" title=""K-vertex-connected graph""><span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-vertex-connected graphs</a> (removing fewer than <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> vertices cannot disconnect the graph), and <a href=""https://en.wikipedia.org/wiki/K-edge-connected_graph"" title=""K-edge-connected graph""><span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-edge-connected graphs</a> (removing fewer than <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> edges cannot disconnect the graph).</dd>
"
converse (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The converse graph is a synonym for the transpose graph; see <a href=""#transpose""><span title=""See entry on this page at § transpose"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">transpose</span></a>.</dd>
"
core (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/K-core"" class=""mw-redirect"" title=""K-core""><span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-core</a> is the induced subgraph formed by removing all vertices of degree less than <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>, and all vertices whose degree becomes less than <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> after earlier removals. See <a href=""#degeneracy""><span title=""See entry on this page at § degeneracy"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">degeneracy</span></a>.</dd>
<dd class=""glossary"">2.  A <a href=""https://en.wikipedia.org/wiki/Core_(graph_theory)"" title=""Core (graph theory)"">core</a> is a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> such that every <a href=""https://en.wikipedia.org/wiki/Graph_homomorphism"" title=""Graph homomorphism"">graph homomorphism</a> from <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> to itself is an isomorphism.</dd>
<dd class=""glossary"">3.  The <a href=""https://en.wikipedia.org/wiki/Core_(graph_theory)"" title=""Core (graph theory)"">core</a> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is a minimal graph <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> such that there exist homomorphisms from <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> to <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> and vice versa. <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> is unique up to isomorphism. It can be represented as an induced subgraph of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, and is a core in the sense that all of its self-homomorphisms are isomorphisms.</dd>
<dd class=""glossary"">4.  In the theory of graph matchings, the core of a graph is an aspect of its <a href=""https://en.wikipedia.org/wiki/Dulmage%E2%80%93Mendelsohn_decomposition"" title=""Dulmage–Mendelsohn decomposition"">Dulmage–Mendelsohn decomposition</a>, formed as the union of all maximum matchings.</dd>
"
cotree (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  The complement of a <a href=""https://en.wikipedia.org/wiki/Spanning_tree"" title=""Spanning tree"">spanning tree</a>.</dd>
<dd class=""glossary"">2.  A rooted tree structure used to describe a <a href=""https://en.wikipedia.org/wiki/Cograph"" title=""Cograph"">cograph</a>, in which each cograph vertex is a leaf of the tree, each internal node of the tree is labeled with 0 or 1, and two cograph vertices are adjacent if and only if their lowest common ancestor in the tree is labeled 1.</dd>
"
cover (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Vertex_cover"" title=""Vertex cover"">vertex cover</a> is a set of vertices incident to every edge in a graph. An <a href=""https://en.wikipedia.org/wiki/Edge_cover"" title=""Edge cover"">edge cover</a> is a set of edges incident to every vertex in a graph.</dd>
"
critical (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A critical graph for a given property is a graph that has the property but such that every subgraph formed by deleting a single vertex does not have the property. For instance, a <a href=""https://en.wikipedia.org/wiki/Factor-critical_graph"" title=""Factor-critical graph"">factor-critical graph</a> is one that has a perfect matching (a 1-factor) for every vertex deletion, but (because it has an odd number of vertices) has no perfect matching itself. Compare <i>hypo-</i>, used for graphs which do not have a property but for which every one-vertex deletion does.</dd>
"
cube (Wikipedia Glossary of Graph Theory Terms)|"
<p>Looks like this term doesn't have a definition yet.</p>
<p>Maybe consider making a contribution to this <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">project</a> or even better improve the original Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a> by making a contribution and <a href=""https://twitter.com/darigovresearch"">let us know</a>!</p>
"
cubic (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  <a href=""https://en.wikipedia.org/wiki/Cube_graph"" class=""mw-redirect"" title=""Cube graph"">Cube graph</a>, the eight-vertex graph of the vertices and edges of a cube.</dd>
<dd class=""glossary"">2.  <a href=""https://en.wikipedia.org/wiki/Hypercube_graph"" title=""Hypercube graph"">Hypercube graph</a>, a higher-dimensional generalization of the cube graph.</dd>
<dd class=""glossary"">3.  <a href=""https://en.wikipedia.org/wiki/Folded_cube_graph"" title=""Folded cube graph"">Folded cube graph</a>, formed from a hypercube by adding a matching connecting opposite vertices.</dd>
<dd class=""glossary"">4.  <a href=""https://en.wikipedia.org/wiki/Halved_cube_graph"" title=""Halved cube graph"">Halved cube graph</a>, the <a href=""https://en.wikipedia.org/wiki/Half-square"" class=""mw-redirect"" title=""Half-square"">half-square</a> of a hypercube graph.</dd>
<dd class=""glossary"">5.  <a href=""https://en.wikipedia.org/wiki/Partial_cube"" title=""Partial cube"">Partial cube</a>, a distance-preserving subgraph of a hypercube.</dd>
<dd class=""glossary"">6.  The cube of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the <a href=""https://en.wikipedia.org/wiki/Graph_power"" title=""Graph power"">graph power</a> <span class=""texhtml""><i>G</i><sup>3</sup></span>.</dd>
<dd class=""glossary"">7.  <a href=""https://en.wikipedia.org/wiki/Cubic_graph"" title=""Cubic graph"">Cubic graph</a>, another name for a <span class=""texhtml"">3</span>-regular graph, one in which each vertex has three incident edges.</dd>
<dd class=""glossary"">8.  <a href=""https://en.wikipedia.org/wiki/Cube-connected_cycles"" title=""Cube-connected cycles"">Cube-connected cycles</a>, a cubic graph formed by replacing each vertex of a hypercube by a cycle.</dd>
"
cut (Wikipedia Glossary of Graph Theory Terms)|"
<p>Looks like this term doesn't have a definition yet.</p>
<p>Maybe consider making a contribution to this <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">project</a> or even better improve the original Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a> by making a contribution and <a href=""https://twitter.com/darigovresearch"">let us know</a>!</p>
"
cut-set (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Cut_(graph_theory)"" title=""Cut (graph theory)"">cut</a> is a partition of the vertices of a graph into two subsets, or the set (also known as a cut-set) of edges that span such a partition, if that set is non-empty. An edge is said to span the partition if it has endpoints in both subsets. Thus, the removal of a cut-set from a connected graph disconnects it.</dd>
"
cut point (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#articulation_point""><span title=""See entry on this page at § articulation point"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">articulation point</span></a>.</dd>
"
cut space (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Cut_space"" class=""mw-redirect"" title=""Cut space"">cut space</a> of a graph is a <a href=""https://en.wikipedia.org/wiki/GF(2)"" title=""GF(2)"">GF(2)</a>-<a href=""https://en.wikipedia.org/wiki/Vector_space"" title=""Vector space"">vector space</a> having the <a href=""#cut-set""><span title=""See entry on this page at § cut-set"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">cut-set</span></a>s<i> of the graph as its elements and <a href=""https://en.wikipedia.org/wiki/Symmetric_difference"" title=""Symmetric difference"">symmetric difference</a> of sets as its vector addition operation.</i></dd>
"
cycle (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Cycle_(graph_theory)"" title=""Cycle (graph theory)"">cycle</a> may either refer to a closed walk (also called a tour) or more specifically to a closed walk without repeated vertices and consequently edges (also called a simple cycle). In either case, the choice of first vertex is usually considered unimportant: <a href=""https://en.wikipedia.org/wiki/Cyclic_permutation"" title=""Cyclic permutation"">cyclic permutations</a> of the walk produce the same cycle. Important special cases of cycles include <a href=""https://en.wikipedia.org/wiki/Hamiltonian_cycle"" class=""mw-redirect"" title=""Hamiltonian cycle"">Hamiltonian cycles</a>, <a href=""https://en.wikipedia.org/wiki/Induced_cycle"" class=""mw-redirect"" title=""Induced cycle"">induced cycles</a>, <a href=""https://en.wikipedia.org/wiki/Peripheral_cycle"" title=""Peripheral cycle"">peripheral cycles</a>, and the shortest cycle, which defines the <a href=""https://en.wikipedia.org/wiki/Girth_(graph_theory)"" title=""Girth (graph theory)"">girth</a> of a graph. A <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-cycle is a cycle of length <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>; for instance a <span class=""texhtml mvar"" style=""font-style:italic;"">2</span>-cycle is a <a href=""https://en.wikipedia.org/wiki/Digon"" title=""Digon"">digon</a> and a <span class=""texhtml"">3</span>-cycle is a triangle. A <a href=""https://en.wikipedia.org/wiki/Cycle_graph"" title=""Cycle graph"">cycle graph</a> is a graph that is itself a simple cycle; a cycle graph with <span class=""texhtml mvar"" style=""font-style:italic;"">n</span> vertices is commonly denoted <span class=""texhtml""><i>C</i><sub><i>n</i></sub></span>. The <a href=""https://en.wikipedia.org/wiki/Cycle_space"" title=""Cycle space"">cycle space</a> is a <a href=""https://en.wikipedia.org/wiki/Vector_space"" title=""Vector space"">vector space</a> generated by simple cycles in a graph.</dd>
"
DAG (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Abbreviation for <a href=""https://en.wikipedia.org/wiki/Directed_acyclic_graph"" title=""Directed acyclic graph"">directed acyclic graph</a>, a directed graph without any directed cycles.</dd>
"
deck (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The multiset of graphs formed from a single graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> by deleting a single vertex in all possible ways, especially in the context of the <a href=""https://en.wikipedia.org/wiki/Reconstruction_conjecture"" title=""Reconstruction conjecture"">reconstruction conjecture</a>. An edge-deck is formed in the same way by deleting a single edge in all possible ways. The graphs in a deck are also called <i>cards</i>. See also <a href=""#critical""><span title=""See entry on this page at § critical"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">critical</span></a> (graphs that have a property that is not held by any card) and <a href=""#hypo-""><span title=""See entry on this page at § hypo-"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">hypo-</span></a> (graphs that do not have a property that is held by all cards).</dd>
"
decomposition (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#tree_decomposition""><span title=""See entry on this page at § tree decomposition"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">tree decomposition</span></a>, <a href=""#path_decomposition""><span title=""See entry on this page at § path decomposition"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">path decomposition</span></a>, or <a href=""#branch-decomposition""><span title=""See entry on this page at § branch-decomposition"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">branch-decomposition</span></a>.</dd>
"
degenerate (Wikipedia Glossary of Graph Theory Terms)|"
<p>Looks like this term doesn't have a definition yet.</p>
<p>Maybe consider making a contribution to this <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">project</a> or even better improve the original Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a> by making a contribution and <a href=""https://twitter.com/darigovresearch"">let us know</a>!</p>
"
degeneracy (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-degenerate graph is an undirected graph in which every induced subgraph has minimum degree at most <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>. The <a href=""https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)"" title=""Degeneracy (graph theory)"">degeneracy</a> of a graph is the smallest <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> for which it is <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-degenerate. A degeneracy ordering is an ordering of the vertices such that each vertex has minimum degree in the induced subgraph of it and all later vertices; in a degeneracy ordering of a <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-degenerate graph, every vertex has at most <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> later neighbours. Degeneracy is also known as the <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-core number, width, and linkage, and one plus the degeneracy is also called the coloring number or Szekeres–Wilf number. <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-degenerate graphs have also been called <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-inductive graphs.</dd>
"
degree (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  The <a href=""https://en.wikipedia.org/wiki/Degree_(graph_theory)"" title=""Degree (graph theory)"">degree</a> of a vertex in a graph is its number of incident edges.<sup id=""cite_ref-clrs_2-2"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-clrs-2"">[2]</a></sup> The degree of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> (or its maximum degree) is the maximum of the degrees of its vertices, often denoted <span class=""texhtml"">Δ(<i>G</i>)</span>; the minimum degree of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the minimum of its vertex degrees, often denoted <span class=""texhtml""><i>δ</i>(<i>G</i>)</span>. Degree is sometimes called <i>valency</i>; the degree of <span class=""texhtml mvar"" style=""font-style:italic;"">v</span> in <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> may be denoted <span class=""texhtml""><i>d</i><sub><i>G</i></sub>(<i>v</i>)</span>, <span class=""texhtml""><i>d</i>(<i>G</i>)</span>, or <span class=""texhtml"">deg(<i>v</i>)</span>. The total degree is the sum of the degrees of all vertices; by the <a href=""https://en.wikipedia.org/wiki/Handshaking_lemma"" title=""Handshaking lemma"">handshaking lemma</a> it is an even number. The <a href=""https://en.wikipedia.org/wiki/Degree_sequence"" class=""mw-redirect"" title=""Degree sequence"">degree sequence</a> is the collection of degrees of all vertices, in sorted order from largest to smallest. In a directed graph, one may distinguish the in-degree (number of incoming edges) and out-degree (number of outgoing edges).<sup id=""cite_ref-clrs_2-3"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-clrs-2"">[2]</a></sup></dd>
<dd class=""glossary"">2.  The homomorphism degree of a graph is a synonym for its <i>Hadwiger number</i>, the order of the largest clique minor.</dd>
"
Δ, <i>δ</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary""><span class=""texhtml"">Δ(<i>G</i>)</span> (using the Greek letter delta) is the maximum degree of a vertex in <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, and <span class=""texhtml""><i>δ</i>(<i>G</i>)</span> is the minimum degree; see <a href=""#degree""><span title=""See entry on this page at § degree"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">degree</span></a>.</dd>
"
density (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">In a graph of <i>n</i> nodes, the density is the ratio of the number of edges of the graph to the number of edges in a complete graph on <i>n</i> nodes. See <a href=""https://en.wikipedia.org/wiki/Dense_graph"" title=""Dense graph"">dense graph</a>.</dd>
"
depth (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The depth of a node in a rooted tree is the number of edges in the path from the root to the node. For instance, the depth of the root is 0 and the depth of any one of its adjacent nodes is 1. It is the level of a node minus one. Note, however, that some authors instead use <i>depth</i> as a synonym for the <i>level</i> of a node.<sup id=""cite_ref-7"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-7"">[7]</a></sup></dd>
"
diameter (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The diameter of a connected graph is the maximum length of a <a href=""https://en.wikipedia.org/wiki/Shortest_path"" class=""mw-redirect"" title=""Shortest path"">shortest path</a>. That is, it is the maximum of the distances between pairs of vertices in the graph. If the graph has weights on its edges, then its weighted diameter measures path length by the sum of the edge weights along a path, while the unweighted diameter measures path length by the number of edges.
For disconnected graphs, definitions vary: the diameter may be defined as infinite, or as the largest diameter of a connected component, or it may be undefined.</dd>
"
diamond (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Diamond_graph"" title=""Diamond graph"">diamond graph</a> is an undirected graph with four vertices and five edges.</dd>
"
diconnected (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary""><a href=""#strong""><span title=""See entry on this page at § Strong"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">Strong</span></a>ly <a href=""#connected""><span title=""See entry on this page at § connected"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">connected</span></a>. (Not to be confused with <a href=""#disconnected""><span title=""See entry on this page at § disconnected"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">disconnected</span></a>)</dd>
"
digon (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Digon"" title=""Digon"">digon</a> is a simple cycle of length two in a directed graph or a multigraph. Digons cannot occur in <a href=""https://en.wikipedia.org/wiki/Simple_graph"" class=""mw-redirect"" title=""Simple graph"">simple</a> undirected graphs as they require repeating the same edge twice, which violates the definition of <a href=""https://en.wikipedia.org/wiki/Simple_graph"" class=""mw-redirect"" title=""Simple graph"">simple</a>.</dd>
"
digraph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Synonym for <a href=""https://en.wikipedia.org/wiki/Directed_graph"" title=""Directed graph"">directed graph</a>.<sup id=""cite_ref-clrs_2-4"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-clrs-2"">[2]</a></sup></dd>
"
dipath (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#directed_path""><span title=""See entry on this page at § directed path"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">directed path</span></a>.</dd>
"
direct predecessor (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The tail of a directed edge whose head is the given vertex.</dd>
"
direct successor (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The head of a directed edge whose tail is the given vertex.</dd>
"
directed (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Directed_graph"" title=""Directed graph"">directed graph</a> is one in which the edges have a distinguished direction, from one vertex to another.<sup id=""cite_ref-clrs_2-5"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-clrs-2"">[2]</a></sup> In a <a href=""https://en.wikipedia.org/wiki/Mixed_graph"" title=""Mixed graph"">mixed graph</a>, a directed edge is again one that has a distinguished direction; directed edges may also be called arcs or arrows.</dd>
"
directed arc (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#arrow""><span title=""See entry on this page at § arrow"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">arrow</span></a>.</dd>
"
directed edge (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#arrow""><span title=""See entry on this page at § arrow"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">arrow</span></a>.</dd>
"
directed line (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#arrow""><span title=""See entry on this page at § arrow"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">arrow</span></a>.</dd>
"
directed path (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""#path""><span title=""See entry on this page at § path"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">path</span></a> in which all the <i><a href=""#edge""><span title=""See entry on this page at § edge"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">edge</span></a>s</i> have the same <a href=""#direction""><span title=""See entry on this page at § direction"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">direction</span></a>. If a directed path leads from <a href=""#vertex""><span title=""See entry on this page at § vertex"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">vertex</span></a> <span class=""texhtml""><i>x</i></span> to vertex <span class=""texhtml""><i>y</i></span>, <span class=""texhtml""><i>x</i></span> is a <a href=""#predecessor""><span title=""See entry on this page at § predecessor"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">predecessor</span></a> of <span class=""texhtml""><i>y</i></span>, <span class=""texhtml""><i>y</i></span> is a <a href=""#successor""><span title=""See entry on this page at § successor"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">successor</span></a> of <span class=""texhtml""><i>x</i></span>, and <span class=""texhtml""><i>y</i></span> is said to be <a href=""#reachable""><span title=""See entry on this page at § reachable"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">reachable</span></a> from <span class=""texhtml""><i>x</i></span>.</dd>
"
direction (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  The <a href=""https://en.wikipedia.org/wiki/Asymmetric_relation"" title=""Asymmetric relation"">asymmetric relation</a> between two <a href=""#adjacent""><span title=""See entry on this page at § adjacent"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">adjacent</span></a> <a href=""#vertex""><span title=""See entry on this page at § vertex"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">vertices</span></a> in a <a href=""#graph""><span title=""See entry on this page at § graph"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">graph</span></a>, represented as an <a href=""#arrow""><span title=""See entry on this page at § arrow"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">arrow</span></a>.</dd>
<dd class=""glossary"">2.  The asymmetric relation between two vertices in a <a href=""#directed_path""><span title=""See entry on this page at § directed path"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">directed path</span></a>.</dd>
"
disconnect (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Cause to be <a href=""#disconnected""><span title=""See entry on this page at § disconnected"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">disconnected</span></a>.</dd>
"
disconnected (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Not <a href=""#connected""><span title=""See entry on this page at § connected"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">connected</span></a>.</dd>
"
disjoint (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  Two subgraphs are edge disjoint if they share no edges, and vertex disjoint if they share no vertices.</dd>
<dd class=""glossary"">2.  The disjoint union of two or more graphs is a graph whose vertex and edge sets are the <a href=""https://en.wikipedia.org/wiki/Disjoint_union"" title=""Disjoint union"">disjoint unions</a> of the corresponding sets.</dd>
"
distance (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Distance_(graph_theory)"" title=""Distance (graph theory)"">distance</a> between any two vertices in a graph is the length of the shortest path having the two vertices as its endpoints.</dd>
"
domatic (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A domatic partition of a graph is a partition of the vertices into dominating sets. The <a href=""https://en.wikipedia.org/wiki/Domatic_number"" title=""Domatic number"">domatic number</a> of the graph is the maximum number of dominating sets in such a partition.</dd>
"
dominating (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Dominating_set"" title=""Dominating set"">dominating set</a> is a set of vertices that includes or is adjacent to every vertex in the graph; not to be confused with a vertex cover, a vertex set that is incident to all edges in the graph. Important special types of dominating sets include independent dominating sets (dominating sets that are also independent sets) and connected dominating sets (dominating sets that induced connected subgraphs). A single-vertex dominating set may also be called a universal vertex. The domination number of a graph is the number of vertices in the smallest dominating set.</dd>
"
<i>E</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary""><span class=""texhtml""><i>E</i>(<i>G</i>)</span> is the edge set of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>; see <a href=""#edge_set""><span title=""See entry on this page at § edge set"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">edge set</span></a>.</dd>
"
ear (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An ear of a graph is a path whose endpoints may coincide but in which otherwise there are no repetitions of vertices or edges.</dd>
"
ear decomposition (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""https://en.wikipedia.org/wiki/Ear_decomposition"" title=""Ear decomposition"">ear decomposition</a> is a partition of the edges of a graph into a sequence of ears, each of whose endpoints (after the first one) belong to a previous ear and each of whose interior points do not belong to any previous ear. An open ear is a simple path (an ear without repeated vertices), and an open ear decomposition is an ear decomposition in which each ear after the first is open; a graph has an open ear decomposition if and only if it is biconnected. An ear is odd if it has an odd number of edges, and an odd ear decomposition is an ear decomposition in which each ear is odd; a graph has an odd ear decomposition if and only if it is factor-critical.</dd>
"
eccentricity (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The eccentricity of a vertex is the farthest distance from it to any other vertex.</dd>
"
edge (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An edge is (together with vertices) one of the two basic units out of which graphs are constructed. Each edge has two (or in hypergraphs, more) vertices to which it is attached, called its endpoints. Edges may be directed or undirected; undirected edges are also called lines and directed edges are also called arcs or arrows. In an undirected <a href=""https://en.wikipedia.org/wiki/Simple_graph"" class=""mw-redirect"" title=""Simple graph"">simple graph</a>, an edge may be represented as the set of its vertices, and in a directed simple graph it may be represented as an ordered pair of its vertices. An edge that connects vertices <span class=""texhtml mvar"" style=""font-style:italic;"">x</span> and <span class=""texhtml mvar"" style=""font-style:italic;"">y</span> is sometimes written <span class=""texhtml mvar"" style=""font-style:italic;"">xy</span>.</dd>
"
edge cut (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A set of <a href=""#edge""><span title=""See entry on this page at § edge"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">edge</span></a>s<i> whose removal <a href=""#disconnected""><span title=""See entry on this page at § disconnected"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">disconnects</span></a> the <a href=""#graph""><span title=""See entry on this page at § graph"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">graph</span></a>. A one-edge cut is called a <a href=""#bridge""><span title=""See entry on this page at § bridge"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">bridge</span></a>, <a href=""#isthmus""><span title=""See entry on this page at § isthmus"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">isthmus</span></a>, or <a href=""#cut_edge""><span title=""See entry on this page at § cut edge"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">cut edge</span></a>.</i></dd>
"
edge set (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The set of edges of a given graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, sometimes denoted by <span class=""texhtml""><i>E</i>(<i>G</i>)</span>.</dd>
"
edgeless graph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Edgeless_graph"" class=""mw-redirect"" title=""Edgeless graph"">edgeless graph</a> or totally disconnected graph on a given set of vertices is the graph that has no edges. It is sometimes called the empty graph, but this term can also refer to a graph with no vertices.</dd>
"
embedding (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Graph_embedding"" title=""Graph embedding"">graph embedding</a> is a topological representation of a graph as a subset of a topological space with each vertex represented as a point, each edge represented as a curve having the endpoints of the edge as endpoints of the curve, and no other intersections between vertices or edges. A <a href=""https://en.wikipedia.org/wiki/Planar_graph"" title=""Planar graph"">planar graph</a> is a graph that has such an embedding onto the Euclidean plane, and a <a href=""https://en.wikipedia.org/wiki/Toroidal_graph"" title=""Toroidal graph"">toroidal graph</a> is a graph that has such an embedding onto a torus. The <a href=""https://en.wikipedia.org/wiki/Genus_(mathematics)"" title=""Genus (mathematics)"">genus</a> of a graph is the minimum possible genus of a two-dimensional <a href=""https://en.wikipedia.org/wiki/Manifold"" title=""Manifold"">manifold</a> onto which it can be embedded.</dd>
"
empty graph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  An <a href=""https://en.wikipedia.org/wiki/Edgeless_graph"" class=""mw-redirect"" title=""Edgeless graph"">edgeless graph</a> on a nonempty set of vertices.</dd>
<dd class=""glossary"">2.  The <a href=""https://en.wikipedia.org/wiki/Order-zero_graph"" class=""mw-redirect"" title=""Order-zero graph"">order-zero graph</a>, a graph with no vertices and no edges.</dd>
"
end (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""https://en.wikipedia.org/wiki/End_(graph_theory)"" title=""End (graph theory)"">end</a> of an infinite graph is an equivalence class of rays, where two rays are equivalent if there is a third ray that includes infinitely many vertices from both of them.</dd>
"
endpoint (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">One of the two vertices joined by a given edge, or one of the first or last vertex of a walk, trail or path. The first endpoint of a given directed edge is called the <i>tail</i> and the second endpoint is called the <i>head</i>.</dd>
"
enumeration (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary""><a href=""https://en.wikipedia.org/wiki/Graph_enumeration"" title=""Graph enumeration"">Graph enumeration</a> is the problem of counting the graphs in a given class of graphs, as a function of their order. More generally, enumeration problems can refer either to problems of counting a certain class of combinatorial objects (such as cliques, independent sets, colorings, or spanning trees), or of algorithmically listing all such objects.</dd>
"
Eulerian (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""https://en.wikipedia.org/wiki/Eulerian_path"" title=""Eulerian path"">Eulerian path</a> is a walk that uses every edge of a graph exactly once. An Eulerian circuit (also called an Eulerian cycle or an Euler tour) is a closed walk that uses every edge exactly once. An Eulerian graph is a graph that has an Eulerian circuit. For an undirected graph, this means that the graph is connected and every vertex has even degree. For a directed graph, this means that the graph is strongly connected and every vertex has in-degree equal to the out-degree. In some cases, the connectivity requirement is loosened, and a graph meeting only the degree requirements is called Eulerian.</dd>
"
even (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Divisible by two; for instance, an even cycle is a cycle whose length is even.</dd>
"
expander (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""https://en.wikipedia.org/wiki/Expander_graph"" title=""Expander graph"">expander graph</a> is a graph whose edge expansion, vertex expansion, or spectral expansion is bounded away from zero.</dd>
"
expansion (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  The edge expansion, isoperimetric number, or <a href=""https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)"" title=""Cheeger constant (graph theory)"">Cheeger constant</a> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the minimum ratio, over subsets <span class=""texhtml mvar"" style=""font-style:italic;"">S</span> of at most half of the vertices of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, of the number of edges leaving <span class=""texhtml mvar"" style=""font-style:italic;"">S</span> to the number of vertices in <span class=""texhtml mvar"" style=""font-style:italic;"">S</span>.</dd>
<dd class=""glossary"">2.  The vertex expansion, vertex isoperimetric number, or magnification of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the minimum ratio, over subsets <span class=""texhtml mvar"" style=""font-style:italic;"">S</span> of at most half of the vertices of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, of the number of vertices outside but adjacent to <span class=""texhtml mvar"" style=""font-style:italic;"">S</span> to the number of vertices in <span class=""texhtml mvar"" style=""font-style:italic;"">S</span>.</dd>
<dd class=""glossary"">3.  The unique neighbor expansion of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the minimum ratio, over subsets of at most half of the vertices of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>, of the number of vertices outside <span class=""texhtml mvar"" style=""font-style:italic;"">S</span> but adjacent to a unique vertex in <span class=""texhtml mvar"" style=""font-style:italic;"">S</span> to the number of vertices in <span class=""texhtml mvar"" style=""font-style:italic;"">S</span>.</dd>
<dd class=""glossary"">4.  The spectral expansion of a <span class=""texhtml mvar"" style=""font-style:italic;"">d</span>-regular graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the <a href=""https://en.wikipedia.org/wiki/Spectral_gap"" title=""Spectral gap"">spectral gap</a> between the largest eigenvalue <span class=""texhtml mvar"" style=""font-style:italic;"">d</span> of its adjacency matrix and the second-largest eigenvalue.</dd>
<dd class=""glossary"">5.  A family of graphs has <a href=""https://en.wikipedia.org/wiki/Bounded_expansion"" title=""Bounded expansion"">bounded expansion</a> if all its <span class=""texhtml mvar"" style=""font-style:italic;"">r</span>-shallow minors have a ratio of edges to vertices bounded by a function of <span class=""texhtml mvar"" style=""font-style:italic;"">r</span>, and polynomial expansion if the function of <span class=""texhtml mvar"" style=""font-style:italic;"">r</span> is a polynomial.</dd>
"
face (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">In a <a href=""https://en.wikipedia.org/wiki/Planar_graph"" title=""Planar graph"">plane graph</a> or <a href=""https://en.wikipedia.org/wiki/Graph_embedding"" title=""Graph embedding"">graph embedding</a>, a connected component of the subset of the plane or surface of the embedding that is disjoint from the graph. For an embedding in the plane, all but one face will be bounded; the one exceptional face that extends to infinity is called the outer face.</dd>
"
factor (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A factor of a graph is a spanning subgraph: a subgraph that includes all of the vertices of the graph. The term is primarily used in the context of regular subgraphs: a <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-factor is a factor that is <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-regular. In particular, a <span class=""texhtml"">1</span>-factor is the same thing as a perfect matching. A <a href=""https://en.wikipedia.org/wiki/Factor-critical_graph"" title=""Factor-critical graph"">factor-critical graph</a> is a graph for which deleting any one vertex produces a graph with a <span class=""texhtml"">1</span>-factor.</dd>
"
factorization (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Graph_factorization"" title=""Graph factorization"">graph factorization</a> is a partition of the edges of the graph into factors; a <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-factorization is a partition into <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-factors. For instance a <span class=""texhtml"">1</span>-factorization is an edge coloring with the additional property that each vertex is incident to an edge of each color.</dd>
"
family (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A synonym for <a href=""#class""><span title=""See entry on this page at § class"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">class</span></a>.</dd>
"
finite (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A graph is finite if it has a finite number of vertices and a finite number of edges. Many sources assume that all graphs are finite without explicitly saying so. A graph is locally finite if each vertex has a finite number of incident edges. An infinite graph is a graph that is not finite: it has infinitely many vertices, infinitely many edges, or both.</dd>
"
first order (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The first order <a href=""https://en.wikipedia.org/wiki/Logic_of_graphs"" title=""Logic of graphs"">logic of graphs</a> is a form of logic in which variables represent vertices of a graph, and there exists a binary predicate to test whether two vertices are adjacent. To be distinguished from second order logic, in which variables can also represent sets of vertices or edges.</dd>
"
-flap (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">For a set of vertices <span class=""texhtml mvar"" style=""font-style:italic;"">X</span>, an <span class=""texhtml mvar"" style=""font-style:italic;"">X</span>-flap is a connected component of the induced subgraph formed by deleting <span class=""texhtml mvar"" style=""font-style:italic;"">X</span>. The flap terminology is commonly used in the context of <i>havens</i>, functions that map small sets of vertices to their flaps. See also the <a href=""#bridge""><span title=""See entry on this page at § bridge"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">bridge</span></a> of a cycle, which is either a flap of the cycle vertices or a chord of the cycle.</dd>
"
forbidden (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Forbidden_graph_characterization"" title=""Forbidden graph characterization"">forbidden graph characterization</a> is a characterization of a family of graphs as being the graphs that do not have certain other graphs as subgraphs, induced subgraphs, or minors. If <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> is one of the graphs that does not occur as a subgraph, induced subgraph, or minor, then <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> is said to be forbidden.</dd>
"
forest (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Tree_(graph_theory)"" title=""Tree (graph theory)"">forest</a> is an undirected graph without cycles (a disjoint union of unrooted trees), or a directed graph formed as a disjoint union of rooted trees.</dd>
"
Frucht (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  <a href=""https://en.wikipedia.org/wiki/Robert_Frucht"" title=""Robert Frucht"">Robert Frucht</a></dd>
<dd class=""glossary"">2.  The <a href=""https://en.wikipedia.org/wiki/Frucht_graph"" title=""Frucht graph"">Frucht graph</a>, one of the two smallest cubic graphs with no nontrivial symmetries.</dd>
<dd class=""glossary"">3.  <a href=""https://en.wikipedia.org/wiki/Frucht%27s_theorem"" title=""Frucht's theorem"">Frucht's theorem</a> that every finite group is the group of symmetries of a finite graph.</dd>
"
full (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Synonym for <a href=""#induced""><span title=""See entry on this page at § induced"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">induced</span></a>.</dd>
"
functional graph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Functional_graph"" class=""mw-redirect"" title=""Functional graph"">functional graph</a> is a directed graph where every vertex has out-degree one. Equivalently, a functional graph is a maximal directed pseudoforest.</dd>
"
<i>G</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A variable often used to denote a graph.</dd>
"
genus (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The genus of a graph is the minimum genus of a surface onto which it can be embedded; see <a href=""#embedding""><span title=""See entry on this page at § embedding"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">embedding</span></a>.</dd>
"
geodesic (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">As a noun, a geodesic is a synonym for a <a href=""https://en.wikipedia.org/wiki/Shortest_path"" class=""mw-redirect"" title=""Shortest path"">shortest path</a>. When used as an adjective, it means related to shortest paths or shortest path distances.</dd>
"
giant (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">In the theory of <a href=""https://en.wikipedia.org/wiki/Random_graph"" title=""Random graph"">random graphs</a>, a giant component is a connected component that contains a constant fraction of the vertices of the graph. In standard models of random graphs, there is typically at most one giant component.</dd>
"
girth (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Girth_(graph_theory)"" title=""Girth (graph theory)"">girth</a> of a graph is the length of its shortest cycle.</dd>
"
graph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The fundamental object of study in graph theory, a system of vertices connected in pairs by edges. Often subdivided into <a href=""https://en.wikipedia.org/wiki/Directed_graph"" title=""Directed graph"">directed graphs</a> or <a href=""https://en.wikipedia.org/wiki/Undirected_graph"" class=""mw-redirect"" title=""Undirected graph"">undirected graphs</a> according to whether the edges have an orientation or not. <a href=""https://en.wikipedia.org/wiki/Mixed_graph"" title=""Mixed graph"">Mixed graphs</a> include both types of edges.</dd>
"
greedy (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Produced by a <a href=""https://en.wikipedia.org/wiki/Greedy_algorithm"" title=""Greedy algorithm"">greedy algorithm</a>. For instance, a <a href=""https://en.wikipedia.org/wiki/Greedy_coloring"" title=""Greedy coloring"">greedy coloring</a> of a graph is a coloring produced by considering the vertices in some sequence and assigning each vertex the first available color.</dd>
"
Grötzsch (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  <a href=""https://en.wikipedia.org/wiki/Herbert_Gr%C3%B6tzsch"" title=""Herbert Grötzsch"">Herbert Grötzsch</a></dd>
<dd class=""glossary"">2.  The <a href=""https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph"" title=""Grötzsch graph"">Grötzsch graph</a>, the smallest triangle-free graph requiring four colors in any proper coloring.</dd>
<dd class=""glossary"">3.  <a href=""https://en.wikipedia.org/wiki/Gr%C3%B6tzsch%27s_theorem"" title=""Grötzsch's theorem"">Grötzsch's theorem</a> that triangle-free planar graphs can always be colored with at most three colors.</dd>
"
Grundy number (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  The <a href=""https://en.wikipedia.org/wiki/Grundy_number"" title=""Grundy number"">Grundy number</a> of a graph is the maximum number of colors produced by a <a href=""https://en.wikipedia.org/wiki/Greedy_coloring"" title=""Greedy coloring"">greedy coloring</a>, with a badly-chosen vertex ordering.</dd>
"
<i>H</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A variable often used to denote a graph, especially when another graph has already been denoted by <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>.</dd>
"
<i>H</i>-coloring (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <span class=""texhtml mvar"" style=""font-style:italic;"">H</span>-coloring of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> (where <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> is also a graph) is a homomorphism from <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> to <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>.</dd>
"
<i>H</i>-free (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A graph is <span class=""texhtml mvar"" style=""font-style:italic;"">H</span>-free if it does not have an induced subgraph isomorphic to <span class=""texhtml mvar"" style=""font-style:italic;"">H</span>, that is, if <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> is a forbidden induced subgraph. The <span class=""texhtml mvar"" style=""font-style:italic;"">H</span>-free graphs are the family of all graphs (or, often, all finite graphs) that are <span class=""texhtml mvar"" style=""font-style:italic;"">H</span>-free.<sup id=""cite_ref-8"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-8"">[8]</a></sup> For instance the <a href=""https://en.wikipedia.org/wiki/Triangle-free_graph"" title=""Triangle-free graph"">triangle-free graphs</a> are the graphs that do not have a <a href=""https://en.wikipedia.org/wiki/Triangle_graph"" title=""Triangle graph"">triangle graph</a> as a subgraph. The property of being <span class=""texhtml mvar"" style=""font-style:italic;"">H</span>-free is always hereditary. A graph is <span class=""texhtml mvar"" style=""font-style:italic;"">H</span>-minor-free if it does not have a minor isomorphic to <span class=""texhtml mvar"" style=""font-style:italic;"">H</span>.</dd>
"
Hadwiger (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  <a href=""https://en.wikipedia.org/wiki/Hugo_Hadwiger"" title=""Hugo Hadwiger"">Hugo Hadwiger</a></dd>
<dd class=""glossary"">2.  The <a href=""https://en.wikipedia.org/wiki/Hadwiger_number"" title=""Hadwiger number"">Hadwiger number</a> of a graph is the order of the largest complete minor of the graph. It is also called the contraction clique number or the homomorphism degree.</dd>
<dd class=""glossary"">3.  The <a href=""https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)"" title=""Hadwiger conjecture (graph theory)"">Hadwiger conjecture</a> is the conjecture that the Hadwiger number is never less than the chromatic number.</dd>
"
Hamiltonian (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Hamiltonian_path"" title=""Hamiltonian path"">Hamiltonian path</a> or Hamiltonian cycle is a simple spanning path or simple spanning cycle: it covers all of the vertices in the graph exactly once. A graph is Hamiltonian if it contains a Hamiltonian cycle, and traceable if it contains a Hamiltonian path.</dd>
"
haven (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-<a href=""https://en.wikipedia.org/wiki/Haven_(graph_theory)"" title=""Haven (graph theory)"">haven</a> is a function that maps every set <span class=""texhtml mvar"" style=""font-style:italic;"">X</span> of fewer than <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> vertices to one of its flaps, often satisfying additional consistency conditions. The order of a haven is the number <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>. Havens can be used to characterize the treewidth of finite graphs and the ends and Hadwiger numbers of infinite graphs.</dd>
"
height (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  The <i>height</i> of a node in a rooted tree is the number of edges in a maximal path, going away from the root (i.e. its nodes have strictly increasing depth), that starts at that node and ends at a leaf.</dd>
<dd class=""glossary"">2.  The <i>height</i> of a rooted tree is the height of its root. That is, the <i>height</i> of a tree is the number of edges in a longest possible path, going away from the root, that starts at the root and ends at a leaf.</dd>
<dd class=""glossary"">3.  The <i>height</i> of a <a href=""https://en.wikipedia.org/wiki/Directed_acyclic_graph"" title=""Directed acyclic graph"">directed acyclic graph</a> is the maximal length of a directed path in this graph.</dd>
"
hereditary (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Hereditary_property"" title=""Hereditary property"">hereditary property</a> of graphs is a property that is closed under induced subgraphs: if <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> has a hereditary property, then so must every induced subgraph of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>. Compare <a href=""#monotone""><span title=""See entry on this page at § monotone"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">monotone</span></a> (closed under all subgraphs) or <i>minor-closed</i> (closed under minors).</dd>
"
"<a href=""https://en.wikipedia.org/wiki/Hexagon"" title=""Hexagon"">hexagon</a> (Wikipedia Glossary of Graph Theory Terms)"|"
<dd class=""glossary"">A simple cycle consisting of exactly six edges and six vertices.</dd>
"
hole (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A hole is an induced cycle of length four or more. An odd hole is a hole of odd length. An anti-hole is an induced subgraph of order four whose complement is a cycle; equivalently, it is a hole in the complement graph. This terminology is mainly used in the context of perfect graphs, which are characterized by the <a href=""https://en.wikipedia.org/wiki/Strong_perfect_graph_theorem"" title=""Strong perfect graph theorem"">strong perfect graph theorem</a> as being the graphs with no odd holes or odd anti-holes. The hole-free graphs are the same as the <a href=""https://en.wikipedia.org/wiki/Chordal_graph"" title=""Chordal graph"">chordal graphs</a>.</dd>
"
homomorphic equivalence (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Two graphs are <a href=""https://en.wikipedia.org/wiki/Graph_homomorphism"" title=""Graph homomorphism"">homomorphically equivalent</a> if there exist two homomorphisms, one from each graph to the other graph.</dd>
"
homomorphism (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/Graph_homomorphism"" title=""Graph homomorphism"">graph homomorphism</a> is a mapping from the vertex set of one graph to the vertex set of another graph that maps adjacent vertices to adjacent vertices. This type of mapping between graphs is the one that is most commonly used in category-theoretic approaches to graph theory. A proper graph coloring can equivalently be described as a homomorphism to a complete graph.</dd>
<dd class=""glossary"">2.  The homomorphism degree of a graph is a synonym for its <i>Hadwiger number</i>, the order of the largest clique minor.</dd>
"
hyperedge (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An edge in a <a href=""https://en.wikipedia.org/wiki/Hypergraph"" title=""Hypergraph"">hypergraph</a>, having any number of endpoints, in contrast to the requirement that edges of graphs have exactly two endpoints.</dd>
"
hypercube (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Hypercube_graph"" title=""Hypercube graph"">hypercube graph</a> is a graph formed from the vertices and edges of a geometric <a href=""https://en.wikipedia.org/wiki/Hypercube"" title=""Hypercube"">hypercube</a>.</dd>
"
hypergraph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Hypergraph"" title=""Hypergraph"">hypergraph</a> is a generalization of a graph in which each edge (called a hyperedge in this context) may have more than two endpoints.</dd>
"
hypo- (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">This prefix, in combination with a graph property, indicates a graph that does not have the property but such that every subgraph formed by deleting a single vertex does have the property. For instance, a <a href=""https://en.wikipedia.org/wiki/Hypohamiltonian_graph"" title=""Hypohamiltonian graph"">hypohamiltonian graph</a> is one that does not have a Hamiltonian cycle, but for which every one-vertex deletion produces a Hamiltonian subgraph. Compare <a href=""#critical""><span title=""See entry on this page at § critical"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">critical</span></a>, used for graphs which have a property but for which every one-vertex deletion does not.<sup id=""cite_ref-9"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-9"">[9]</a></sup></dd>
"
in-degree (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The number of incoming edges in a directed graph; see <a href=""#degree""><span title=""See entry on this page at § degree"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">degree</span></a>.</dd>
"
incidence (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""https://en.wikipedia.org/wiki/Incidence_(graph)"" title=""Incidence (graph)"">incidence</a> in a graph is a vertex-edge pair such that the vertex is an endpoint of the edge.</dd>
"
incidence matrix (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Incidence_matrix"" title=""Incidence matrix"">incidence matrix</a> of a graph is a matrix whose rows are indexed by vertices of the graph, and whose columns are indexed by edges, with a one in the cell for row <span class=""texhtml mvar"" style=""font-style:italic;"">i</span> and column <span class=""texhtml mvar"" style=""font-style:italic;"">j</span> when vertex <span class=""texhtml mvar"" style=""font-style:italic;"">i</span> and edge <span class=""texhtml mvar"" style=""font-style:italic;"">j</span> are incident, and a zero otherwise.</dd>
"
incident (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  The relation between an edge and one of its endpoints.<sup id=""cite_ref-clrs_2-6"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-clrs-2"">[2]</a></sup></dd>
<dd class=""glossary"">2.  Two edges are said to be incident if they share a vertex. (cf. adjacent)</dd>
"
incomparability (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An incomparability graph is the complement of a <a href=""https://en.wikipedia.org/wiki/Comparability_graph"" title=""Comparability graph"">comparability graph</a>; see <a href=""#comparability""><span title=""See entry on this page at § comparability"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">comparability</span></a>.</dd>
"
independent (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  An <a href=""https://en.wikipedia.org/wiki/Independent_set_(graph_theory)"" title=""Independent set (graph theory)"">independent set</a> is a set of vertices that induces an edgeless subgraph. It may also be called a stable set or a coclique. The <a href=""https://en.wikipedia.org/wiki/Independence_number"" class=""mw-redirect"" title=""Independence number"">independence number</a> <span class=""texhtml""><i>α</i>(<i>G</i>)</span> is the size of the <a href=""https://en.wikipedia.org/wiki/Maximum_independent_set"" class=""mw-redirect"" title=""Maximum independent set"">maximum independent set</a>.</dd>
<dd class=""glossary"">2.  In the <a href=""https://en.wikipedia.org/wiki/Graphic_matroid"" title=""Graphic matroid"">graphic matroid</a> of a graph, a subset of edges is independent if the corresponding subgraph is a tree or forest. In the <a href=""https://en.wikipedia.org/wiki/Bicircular_matroid"" title=""Bicircular matroid"">bicircular matroid</a>, a subset of edges is independent if the corresponding subgraph is a <a href=""https://en.wikipedia.org/wiki/Pseudoforest"" title=""Pseudoforest"">pseudoforest</a>.</dd>
"
indifference (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""https://en.wikipedia.org/wiki/Indifference_graph"" title=""Indifference graph"">indifference graph</a> is another name for a proper interval graph or unit interval graph; see <a href=""#proper""><span title=""See entry on this page at § proper"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">proper</span></a>.</dd>
"
induced (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""https://en.wikipedia.org/wiki/Induced_subgraph"" title=""Induced subgraph"">induced subgraph</a> or full subgraph of a graph is a subgraph formed from a subset of vertices and from all of the edges that have both endpoints in the subset. Special cases include <a href=""https://en.wikipedia.org/wiki/Induced_path"" title=""Induced path"">induced paths</a> and <a href=""https://en.wikipedia.org/wiki/Induced_cycle"" class=""mw-redirect"" title=""Induced cycle"">induced cycles</a>, induced subgraphs that are paths or cycles.</dd>
"
inductive (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Synonym for <a href=""#degenerate""><span title=""See entry on this page at § degenerate"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">degenerate</span></a>.</dd>
"
infinite (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An infinite graph is one that is not finite; see <a href=""#finite""><span title=""See entry on this page at § finite"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">finite</span></a>.</dd>
"
internal (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A vertex of a path or tree is internal if it is not a leaf; that is, if its degree is greater than one. Two paths are internally disjoint (some people call it <i>independent</i>) if they do not have any vertex in common, except the first and last ones.</dd>
"
intersection (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  The intersection of two graphs is their largest common subgraph, the graph formed by the vertices and edges that belong to both graphs.</dd>
<dd class=""glossary"">2.  An <a href=""https://en.wikipedia.org/wiki/Intersection_graph"" title=""Intersection graph"">intersection graph</a> is a graph whose vertices correspond to sets or geometric objects, with an edge between two vertices exactly when the corresponding two sets or objects have a nonempty intersection. Several classes of graphs may be defined as the intersection graphs of certain types of objects, for instance <a href=""https://en.wikipedia.org/wiki/Chordal_graph"" title=""Chordal graph"">chordal graphs</a> (intersection graphs of subtrees of a tree), <a href=""https://en.wikipedia.org/wiki/Circle_graph"" title=""Circle graph"">circle graphs</a> (intersection graphs of chords of a circle), <a href=""https://en.wikipedia.org/wiki/Interval_graph"" title=""Interval graph"">interval graphs</a> (intersection graphs of intervals of a line), <a href=""https://en.wikipedia.org/wiki/Line_graph"" title=""Line graph"">line graphs</a> (intersection graphs of the edges of a graph), and <a href=""https://en.wikipedia.org/wiki/Clique_graph"" title=""Clique graph"">clique graphs</a> (intersection graphs of the maximal cliques of a graph). Every graph is an intersection graph for some family of sets, and this family is called an intersection representation of the graph. The <a href=""https://en.wikipedia.org/wiki/Intersection_number"" title=""Intersection number"">intersection number</a> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the minimum total number of elements in any intersection representation of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>.</dd>
"
interval (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""https://en.wikipedia.org/wiki/Interval_graph"" title=""Interval graph"">interval graph</a> is an <a href=""https://en.wikipedia.org/wiki/Intersection_graph"" title=""Intersection graph"">intersection graph</a> of <a href=""https://en.wikipedia.org/wiki/Interval_(mathematics)"" title=""Interval (mathematics)"">intervals of a line</a>.</dd>
"
interval thickness (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A synonym for <a href=""#pathwidth""><span title=""See entry on this page at § pathwidth"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">pathwidth</span></a>.</dd>
"
invariant (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A synonym of <a href=""#property""><span title=""See entry on this page at § property"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">pathwidth</span></a>.</dd>
"
inverted arrow (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""#arrow""><span title=""See entry on this page at § arrow"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">arrow</span></a> with an opposite <a href=""#direction""><span title=""See entry on this page at § direction"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">direction</span></a> compared to another arrow. The arrow <span class=""texhtml"">(<i>y</i>, <i>x</i>)</span> is the inverted arrow of the arrow <span class=""texhtml"">(<i>x</i>, <i>y</i>)</span>.</dd>
"
isolated (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An isolated vertex of a graph is a vertex whose degree is zero, that is, a vertex with no incident edges.<sup id=""cite_ref-clrs_2-7"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-clrs-2"">[2]</a></sup></dd>
"
isomorphic (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Two graphs are isomorphic if there is an isomorphism between them; see <a href=""#isomorphism""><span title=""See entry on this page at § isomorphism"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">isomorphism</span></a>.</dd>
"
isomorphism (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Graph_isomorphism"" title=""Graph isomorphism"">graph isomorphism</a> is a one-to-one incidence preserving correspondence of the vertices and edges of one graph to the vertices and edges of another graph. Two graphs related in this way are said to be isomorphic.</dd>
"
isoperimetric (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#expansion""><span title=""See entry on this page at § expansion"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">expansion</span></a>.</dd>
"
isthmus (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Synonym for <a href=""#bridge""><span title=""See entry on this page at § bridge"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">bridge</span></a>, in the sense of an edge whose removal disconnects the graph.</dd>
"
<i>K</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">For the notation for complete graphs, complete bipartite graphs, and complete multipartite graphs, see <a href=""#complete""><span title=""See entry on this page at § complete"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">complete</span></a>.</dd>
"
<i>κ</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary""><span class=""texhtml""><i>κ</i>(<i>G</i>)</span> (using the Greek letter kappa) is the order of the <a href=""https://en.wikipedia.org/wiki/Maximum_clique"" class=""mw-redirect"" title=""Maximum clique"">maximum clique</a> in <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>; see <a href=""#clique""><span title=""See entry on this page at § clique"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">clique</span></a>.</dd>
"
knot (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An inescapable section of a <a href=""#directed_graph""><span title=""See entry on this page at § directed graph"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">directed graph</span></a>. See <a href=""https://en.wikipedia.org/wiki/Knot_(mathematics)"" title=""Knot (mathematics)"">knot (mathematics)</a> and <a href=""https://en.wikipedia.org/wiki/Knot_theory"" title=""Knot theory"">knot theory</a>.</dd>
"
<i>L</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary""><span class=""texhtml""><i>L</i>(<i>G</i>)</span> is the <a href=""https://en.wikipedia.org/wiki/Line_graph"" title=""Line graph"">line graph</a> of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>; see <a href=""#line""><span title=""See entry on this page at § line"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">line</span></a>.</dd>
"
label (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  Information associated with a vertex or edge of a graph. A labeled graph is a graph whose vertices or edges have labels. The terms <i>vertex-labeled</i> or <i>edge-labeled</i> may be used to specify which objects of a graph have labels. <a href=""https://en.wikipedia.org/wiki/Graph_labeling"" title=""Graph labeling"">Graph labeling</a> refers to several different problems of assigning labels to graphs subject to certain constraints. See also <a href=""https://en.wikipedia.org/wiki/Graph_coloring"" title=""Graph coloring"">graph coloring</a>, in which the labels are interpreted as colors.</dd>
<dd class=""glossary"">2.  In the context of <a href=""https://en.wikipedia.org/wiki/Graph_enumeration"" title=""Graph enumeration"">graph enumeration</a>, the vertices of a graph are said to be labeled if they are all distinguishable from each other. For instance, this can be made to be true by fixing a one-to-one correspondence between the vertices and the integers from 1 to the order of the graph. When vertices are labeled, graphs that are isomorphic to each other (but with different vertex orderings) are counted as separate objects. In contrast, when the vertices are unlabeled, graphs that are isomorphic to each other are not counted separately.</dd>
"
leaf (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A leaf vertex or pendant vertex (especially in a tree) is a vertex whose degree is <span class=""texhtml"">1</span>. A leaf edge or pendant edge is the edge connecting a leaf vertex to its single neighbour.</dd>
<dd class=""glossary"">2.  A <a href=""https://en.wikipedia.org/wiki/Leaf_power"" title=""Leaf power"">leaf power</a> of a tree is a graph whose vertices are the leaves of the tree and whose edges connect leaves whose distance in the tree is at most a given threshold.</dd>
"
length (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">In an unweighted graph, the length of a cycle, path, or walk is the number of edges it uses. In a weighted graph, it may instead be the sum of the weights of the edges that it uses. Length is used to define the <a href=""https://en.wikipedia.org/wiki/Shortest_path"" class=""mw-redirect"" title=""Shortest path"">shortest path</a>, <a href=""https://en.wikipedia.org/wiki/Girth_(graph_theory)"" title=""Girth (graph theory)"">girth</a> (shortest cycle length), and <a href=""https://en.wikipedia.org/wiki/Longest_path"" class=""mw-redirect"" title=""Longest path"">longest path</a> between two vertices in a graph.</dd>
"
level (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  This is the <i>depth</i> of a node plus 1, although some<sup id=""cite_ref-NIST_Level_10-0"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-NIST_Level-10"">[10]</a></sup> define it instead to be synonym of <i>depth</i>. A node's level in a rooted tree is the number of nodes in the path from the root to the node. For instance, the root has level 1 and any one of its adjacent nodes has level 2. </dd>
<dd class=""glossary"">2.  A set of all node having the same level or depth.<sup id=""cite_ref-NIST_Level_10-1"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-NIST_Level-10"">[10]</a></sup></dd>
"
line (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A synonym for an undirected edge. The <a href=""https://en.wikipedia.org/wiki/Line_graph"" title=""Line graph"">line graph</a> <span class=""texhtml""><i>L</i>(<i>G</i>)</span> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is a graph with a vertex for each edge of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> and an edge for each pair of edge that share an endpoint in <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>.</dd>
"
linkage (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A synonym for <a href=""#degeneracy""><span title=""See entry on this page at § degeneracy"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">degeneracy</span></a>.</dd>
"
list (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  An <a href=""https://en.wikipedia.org/wiki/Adjacency_list"" title=""Adjacency list"">adjacency list</a> is a computer representation of graphs for use in graph algorithms.</dd>
<dd class=""glossary"">2.  <a href=""https://en.wikipedia.org/wiki/List_coloring"" title=""List coloring"">List coloring</a> is a variation of graph coloring in which each vertex has a list of available colors.</dd>
"
local (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A local property of a graph is a property that is determined only by the <a href=""https://en.wikipedia.org/wiki/Neighbourhood_(graph_theory)"" title=""Neighbourhood (graph theory)"">neighbourhoods</a> of the vertices in the graph. For instance, a graph is locally finite if all of its neighborhoods are finite.</dd>
"
loop (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Loop_(graph_theory)"" title=""Loop (graph theory)"">loop</a> or self-loop is an edge both of whose endpoints are the same vertex. It forms a cycle of length <span class=""texhtml"">1</span>. These are not allowed in simple graphs.</dd>
"
magnification (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Synonym for vertex <a href=""#expansion""><span title=""See entry on this page at § expansion"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">expansion</span></a>.</dd>
"
matching (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Matching_(graph_theory)"" title=""Matching (graph theory)"">matching</a> is a set of edges in which no two share any vertex. A vertex is matched or saturated if it is one of the endpoints of an edge in the matching. A <a href=""https://en.wikipedia.org/wiki/Perfect_matching"" class=""mw-redirect"" title=""Perfect matching"">perfect matching</a> or complete matching is a matching that matches every vertex; it may also be called a 1-factor, and can only exist when the order is even. A near-perfect matching, in a graph with odd order, is one that saturates all but one vertex. A <a href=""https://en.wikipedia.org/wiki/Maximum_matching"" class=""mw-redirect"" title=""Maximum matching"">maximum matching</a> is a matching that uses as many edges as possible; the matching number <span class=""texhtml""><i>α</i>′(<i>G</i>)</span> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the number of edges in a maximum matching. A <a href=""https://en.wikipedia.org/wiki/Maximal_matching"" class=""mw-redirect"" title=""Maximal matching"">maximal matching</a> is a matching to which no additional edges can be added.</dd>
"
maximal (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A subgraph of given graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is maximal for a particular property if it has that property but no other supergraph of it that is also a subgraph of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> also has the same property. That is, it is a <a href=""https://en.wikipedia.org/wiki/Maximal_element"" class=""mw-redirect"" title=""Maximal element"">maximal element</a> of the subgraphs with the property. For instance, a <a href=""https://en.wikipedia.org/wiki/Maximal_clique"" class=""mw-redirect"" title=""Maximal clique"">maximal clique</a> is a complete subgraph that cannot be expanded to a larger complete subgraph. The word ""maximal"" should be distinguished from ""maximum"": a maximum subgraph is always maximal, but not necessarily vice versa.</dd>
<dd class=""glossary"">2.  A simple graph with a given property is maximal for that property if it is not possible to add any more edges to it (keeping the vertex set unchanged) while preserving both the simplicity of the graph and the property. Thus, for instance, a <a href=""https://en.wikipedia.org/wiki/Maximal_planar_graph"" class=""mw-redirect"" title=""Maximal planar graph"">maximal planar graph</a> is a planar graph such that adding any more edges to it would create a non-planar graph.</dd>
"
maximum (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A subgraph of a given graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is maximum for a particular property if it is the largest subgraph (by order or size) among all subgraphs with that property. For instance, a <a href=""https://en.wikipedia.org/wiki/Maximum_clique"" class=""mw-redirect"" title=""Maximum clique"">maximum clique</a> is any of the largest cliques in a given graph.</dd>
"
median (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A median of a triple of vertices, a vertex that belongs to shortest paths between all pairs of vertices, especially in median graphs and <a href=""https://en.wikipedia.org/wiki/Modular_graph"" title=""Modular graph"">modular graphs</a>.</dd>
<dd class=""glossary"">2.  A <a href=""https://en.wikipedia.org/wiki/Median_graph"" title=""Median graph"">median graph</a> is a graph in which every three vertices have a unique median.</dd>
"
Meyniel (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  Henri Meyniel, French graph theorist.</dd>
<dd class=""glossary"">2.  A <a href=""https://en.wikipedia.org/wiki/Meyniel_graph"" title=""Meyniel graph"">Meyniel graph</a> is a graph in which every odd cycle of length five or more has at least two chords.</dd>
"
minimal (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A subgraph of given graph is minimal for a particular property if it has that property but no proper subgraph of it also has the same property. That is, it is a <a href=""https://en.wikipedia.org/wiki/Minimal_element"" class=""mw-redirect"" title=""Minimal element"">minimal element</a> of the subgraphs with the property.</dd>
"
"<a href=""https://en.wikipedia.org/wiki/Minimum_cut"" title=""Minimum cut"">minimum cut</a> (Wikipedia Glossary of Graph Theory Terms)"|"
<dd class=""glossary"">A <a href=""#cut""><span title=""See entry on this page at § cut"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">cut</span></a> whose <a href=""#cut-set""><span title=""See entry on this page at § cut-set"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">cut-set</span></a> has minimum total weight, possibly restricted to cuts that separate a designated pair of vertices; they are characterized by the <a href=""https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem"" title=""Max-flow min-cut theorem"">max-flow min-cut theorem</a>.</dd>
"
minor (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A graph <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> is a <a href=""https://en.wikipedia.org/wiki/Graph_minor"" title=""Graph minor"">minor</a> of another graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> if <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> can be obtained by deleting edges or vertices from <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> and contracting edges in <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>. It is a <a href=""https://en.wikipedia.org/wiki/Shallow_minor"" title=""Shallow minor"">shallow minor</a> if it can be formed as a minor in such a way that the subgraphs of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> that were contracted to form vertices of <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> all have small diameter. <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> is a <a href=""https://en.wikipedia.org/wiki/Topological_minor"" class=""mw-redirect"" title=""Topological minor"">topological minor</a> of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> if <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> has a subgraph that is a <a href=""https://en.wikipedia.org/wiki/Subdivision_(graph_theory)"" class=""mw-redirect"" title=""Subdivision (graph theory)"">subdivision</a> of <span class=""texhtml mvar"" style=""font-style:italic;"">H</span>. A graph is <span class=""texhtml mvar"" style=""font-style:italic;"">H</span>-minor-free if it does not have <span class=""texhtml mvar"" style=""font-style:italic;"">H</span> as a minor. A family of graphs is minor-closed if it is closed under minors; the <a href=""https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem"" title=""Robertson–Seymour theorem"">Robertson–Seymour theorem</a> characterizes minor-closed families as having a finite set of <a href=""#forbidden""><span title=""See entry on this page at § forbidden"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">forbidden</span></a> minors.</dd>
"
mixed (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Mixed_graph"" title=""Mixed graph"">mixed graph</a> is a graph that may include both directed and undirected edges.</dd>
"
modular (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  <a href=""https://en.wikipedia.org/wiki/Modular_graph"" title=""Modular graph"">Modular graph</a>, a graph in which each triple of vertices has at least one median vertex that belongs to shortest paths between all pairs of the triple.</dd>
<dd class=""glossary"">2.  <a href=""https://en.wikipedia.org/wiki/Modular_decomposition"" title=""Modular decomposition"">Modular decomposition</a>, a decomposition of a graph into subgraphs within which all vertices connect to the rest of the graph in the same way.</dd>
<dd class=""glossary"">3.  <a href=""https://en.wikipedia.org/wiki/Modularity_(networks)"" title=""Modularity (networks)"">Modularity</a> of a graph clustering, the difference of the number of cross-cluster edges from its expected value.</dd>
"
monotone (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A monotone property of graphs is a property that is closed under subgraphs: if <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> has a hereditary property, then so must every subgraph of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>. Compare <a href=""#hereditary""><span title=""See entry on this page at § hereditary"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">hereditary</span></a> (closed under induced subgraphs) or <i>minor-closed</i> (closed under minors).</dd>
"
Moore graph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Moore_graph"" title=""Moore graph"">Moore graph</a> is a regular graph for which the Moore bound is met exactly. The Moore bound is an inequality relating the degree, diameter, and order of a graph, proved by <a href=""https://en.wikipedia.org/wiki/Edward_F._Moore"" title=""Edward F. Moore"">Edward F. Moore</a>. Every Moore graph is a cage.</dd>
"
multigraph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Multigraph"" title=""Multigraph"">multigraph</a> is a graph that allows multiple adjacencies (and, often, self-loops); a graph that is not required to be simple.</dd>
"
multiple adjacency (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A multiple adjacency or multiple edge is a set of more than one edge that all have the same endpoints (in the same direction, in the case of directed graphs). A graph with multiple edges is often called a multigraph.</dd>
"
multiplicity (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The multiplicity of an edge is the number of edges in a multiple adjacency. The multiplicity of a graph is the maximum multiplicity of any of its edges.</dd>
"
<i>N</i> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  For the notation for open and closed neighborhoods, see <a href=""#neighbourhood""><span title=""See entry on this page at § neighbourhood"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">neighbourhood</span></a>.</dd>
<dd class=""glossary"">2.  A lower-case <span class=""texhtml mvar"" style=""font-style:italic;"">n</span> is often used (especially in computer science) to denote the number of vertices in a given graph.</dd>
"
neighbor (Wikipedia Glossary of Graph Theory Terms)|"
<p>Looks like this term doesn't have a definition yet.</p>
<p>Maybe consider making a contribution to this <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">project</a> or even better improve the original Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a> by making a contribution and <a href=""https://twitter.com/darigovresearch"">let us know</a>!</p>
"
neighbour (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A vertex that is adjacent to a given vertex.</dd>
"
neighborhood (Wikipedia Glossary of Graph Theory Terms)|"
<p>Looks like this term doesn't have a definition yet.</p>
<p>Maybe consider making a contribution to this <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">project</a> or even better improve the original Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a> by making a contribution and <a href=""https://twitter.com/darigovresearch"">let us know</a>!</p>
"
neighbourhood (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Neighbourhood_(graph_theory)"" title=""Neighbourhood (graph theory)"">open neighbourhood</a> (or neighborhood) of a vertex <span class=""texhtml mvar"" style=""font-style:italic;"">v</span> is the subgraph induced by all vertices that are adjacent to <span class=""texhtml mvar"" style=""font-style:italic;"">v</span>. The closed neighbourhood is defined in the same way but also includes <span class=""texhtml mvar"" style=""font-style:italic;"">v</span> itself. The open neighborhood of <span class=""texhtml mvar"" style=""font-style:italic;"">v</span> in <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> may be denoted <span class=""texhtml""><i>N</i><sub><i>G</i></sub>(<i>v</i>)</span> or <span class=""texhtml""><i>N</i>(<i>v</i>)</span>, and the closed neighborhood may be denoted <span class=""texhtml""><i>N</i><sub><i>G</i></sub>[<i>v</i>]</span> or <span class=""texhtml""><i>N</i>[<i>v</i>]</span>. When the openness or closedness of a neighborhood is not specified, it is assumed to be open.</dd>
"
network (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A graph in which attributes (e.g. names) are associated with the nodes and/or edges.</dd>
"
node (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A synonym for <a href=""#vertex""><span title=""See entry on this page at § vertex"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">vertex</span></a>.</dd>
"
non-edge (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A non-edge or anti-edge is a pair of vertices that are not adjacent; the edges of the complement graph.</dd>
"
null graph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#empty_graph""><span title=""See entry on this page at § empty graph"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">empty graph</span></a>.</dd>
"
odd (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  An odd cycle is a cycle whose length is odd. The <a href=""https://en.wikipedia.org/wiki/Girth_(graph_theory)"" title=""Girth (graph theory)"">odd girth</a> of a non-bipartite graph is the length of its shortest odd cycle. An odd hole is a special case of an odd cycle: one that is induced and has four or more vertices.</dd>
<dd class=""glossary"">2.  An odd vertex is a vertex whose degree is odd. By the <a href=""https://en.wikipedia.org/wiki/Handshaking_lemma"" title=""Handshaking lemma"">handshaking lemma</a> every finite undirected graph has an even number of odd vertices.</dd>
<dd class=""glossary"">3.  An odd ear is a simple path or simple cycle with an odd number of edges, used in odd ear decompositions of factor-critical graphs; see <a href=""#ear""><span title=""See entry on this page at § ear"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">ear</span></a>.</dd>
<dd class=""glossary"">4.  An odd chord is an edge connecting two vertices that are an odd distance apart in an even cycle. Odd chords are used to define <a href=""https://en.wikipedia.org/wiki/Strongly_chordal_graph"" title=""Strongly chordal graph"">strongly chordal graphs</a>.</dd>
<dd class=""glossary"">5.  An <a href=""https://en.wikipedia.org/wiki/Odd_graph"" title=""Odd graph"">odd graph</a> is a special case of a <a href=""https://en.wikipedia.org/wiki/Kneser_graph"" title=""Kneser graph"">Kneser graph</a>, having one vertex for each <span class=""texhtml"">(<i>n</i> − 1)</span>-element subset of a <span class=""texhtml"">(2<i>n</i> − 1)</span>-element set, and an edge connecting two subsets when their corresponding sets are disjoint.</dd>
"
open (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  See <a href=""#neighbourhood""><span title=""See entry on this page at § neighbourhood"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">neighbourhood</span></a>.</dd>
<dd class=""glossary"">2.  See <a href=""#walk""><span title=""See entry on this page at § walk"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">walk</span></a>.</dd>
"
<span id=""order"">order</span> (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  The order of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the number of its vertices, <span class=""texhtml"">|<i>V</i>(<i>G</i>)|</span>. The variable <span class=""texhtml mvar"" style=""font-style:italic;"">n</span> is often used for this quantity. See also <a href=""#size""><span title=""See entry on this page at § size"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">size</span></a>, the number of edges.</dd>
<dd class=""glossary"">2.  A type of <a href=""https://en.wikipedia.org/wiki/Logic_of_graphs"" title=""Logic of graphs"">logic of graphs</a>; see <a href=""#first_order""><span title=""See entry on this page at § first order"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">first order</span></a> and <a href=""#second_order""><span title=""See entry on this page at § second order"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">second order</span></a>.</dd>
<dd class=""glossary"">3.  An order or ordering of a graph is an arrangement of its vertices into a sequence, especially in the context of <a href=""https://en.wikipedia.org/wiki/Topological_ordering"" class=""mw-redirect"" title=""Topological ordering"">topological ordering</a> (an order of a directed acyclic graph in which every edge goes from an earlier vertex to a later vertex in the order) and <a href=""https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)"" title=""Degeneracy (graph theory)"">degeneracy ordering</a> (an order in which each vertex has minimum degree in the induced subgraph of it and all later vertices).</dd>
<dd class=""glossary"">4.  For the order of a haven or bramble, see <a href=""#haven""><span title=""See entry on this page at § haven"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">haven</span></a> and <a href=""#bramble""><span title=""See entry on this page at § bramble"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">bramble</span></a>.</dd>
"
orientation (Wikipedia Glossary of Graph Theory Terms)|"
<p>Looks like this term doesn't have a definition yet.</p>
<p>Maybe consider making a contribution to this <a href=""https://github.com/darigovresearch/Wikipedia-Glossary-of-Graph-Theory-Terms-Flashcards"">project</a> or even better improve the original Wikipedia article <a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms"">""Glossary of graph theory terms""</a> by making a contribution and <a href=""https://twitter.com/darigovresearch"">let us know</a>!</p>
"
oriented (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  An <a href=""https://en.wikipedia.org/wiki/Orientation_(graph_theory)"" title=""Orientation (graph theory)"">orientation</a> of an undirected graph is an assignment of directions to its edges, making it into a directed graph. An oriented graph is one that has been assigned an orientation. So, for instance, a <a href=""https://en.wikipedia.org/wiki/Polytree"" title=""Polytree"">polytree</a> is an oriented tree; it differs from a directed tree (an arborescence) in that there is no requirement of consistency in the directions of its edges. Other special types of orientation include <a href=""https://en.wikipedia.org/wiki/Tournament_(graph_theory)"" title=""Tournament (graph theory)"">tournaments</a>, orientations of complete graphs; <a href=""https://en.wikipedia.org/wiki/Strong_orientation"" title=""Strong orientation"">strong orientations</a>, orientations that are strongly connected; <a href=""https://en.wikipedia.org/wiki/Acyclic_orientation"" title=""Acyclic orientation"">acyclic orientations</a>, orientations that are acyclic; <a href=""https://en.wikipedia.org/wiki/Eulerian_path"" title=""Eulerian path"">Eulerian orientations</a>, orientations that are Eulerian; and <a href=""https://en.wikipedia.org/wiki/Transitive_orientation"" class=""mw-redirect"" title=""Transitive orientation"">transitive orientations</a>, orientations that are transitively closed.</dd>
<dd class=""glossary"">2.  Oriented graph, used by some authors as a synonym for a <a href=""https://en.wikipedia.org/wiki/Directed_graph"" title=""Directed graph"">directed graph</a>.</dd>
"
out-degree (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#degree""><span title=""See entry on this page at § degree"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">degree</span></a>.</dd>
"
outer (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#face""><span title=""See entry on this page at § face"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">face</span></a>.</dd>
"
outerplanar (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">An <a href=""https://en.wikipedia.org/wiki/Outerplanar_graph"" title=""Outerplanar graph"">outerplanar graph</a> is a graph that can be embedded in the plane (without crossings) so that all vertices are on the outer face of the graph.</dd>
"
path (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Path_(graph_theory)"" title=""Path (graph theory)"">path</a> may either be a walk or a walk without repeated vertices and consequently edges (also called a simple path), depending on the source. Important special cases include <a href=""https://en.wikipedia.org/wiki/Induced_path"" title=""Induced path"">induced paths</a> and <a href=""https://en.wikipedia.org/wiki/Shortest_path"" class=""mw-redirect"" title=""Shortest path"">shortest paths</a>.</dd>
"
path decomposition (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Path_decomposition"" class=""mw-redirect"" title=""Path decomposition"">path decomposition</a> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is a tree decomposition whose underlying tree is a path. Its width is defined in the same way as for tree decompositions, as one less than the size of the largest bag. The minimum width of any path decomposition of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the pathwidth of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>.</dd>
"
pathwidth (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Pathwidth"" title=""Pathwidth"">pathwidth</a> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the minimum width of a path decomposition of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>. It may also be defined in terms of the clique number of an interval completion of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>. It is always between the bandwidth and the treewidth of <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>. It is also known as interval thickness, vertex separation number, or node searching number.</dd>
"
pendant (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#leaf""><span title=""See entry on this page at § leaf"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">leaf</span></a>.</dd>
"
perfect (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/Perfect_graph"" title=""Perfect graph"">perfect graph</a> is a graph in which, in every induced subgraph, the chromatic number equals the clique number. The <a href=""https://en.wikipedia.org/wiki/Perfect_graph_theorem"" title=""Perfect graph theorem"">perfect graph theorem</a> and <a href=""https://en.wikipedia.org/wiki/Strong_perfect_graph_theorem"" title=""Strong perfect graph theorem"">strong perfect graph theorem</a> are two theorems about perfect graphs, the former proving that their complements are also perfect and the latter proving that they are exactly the graphs with no odd holes or anti-holes.</dd>
<dd class=""glossary"">2.  A <a href=""https://en.wikipedia.org/wiki/Perfectly_orderable_graph"" title=""Perfectly orderable graph"">perfectly orderable graph</a> is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with this ordering optimally colors every induced subgraph. The perfectly orderable graphs are a subclass of the perfect graphs.</dd>
<dd class=""glossary"">3.  A <a href=""https://en.wikipedia.org/wiki/Perfect_matching"" class=""mw-redirect"" title=""Perfect matching"">perfect matching</a> is a matching that saturates every vertex; see <a href=""#matching""><span title=""See entry on this page at § matching"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">matching</span></a>.</dd>
<dd class=""glossary"">4.  A perfect <a href=""https://en.wikipedia.org/wiki/1-factorization"" class=""mw-redirect"" title=""1-factorization"">1-factorization</a> is a partition of the edges of a graph into perfect matchings so that each two matchings form a Hamiltonian cycle.</dd>
"
peripheral (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/Peripheral_cycle"" title=""Peripheral cycle"">peripheral cycle</a> or non-separating cycle is a cycle with at most one bridge.</dd>
<span id=""peripheral_vertex""></span><dd class=""glossary"">2.  A peripheral vertex is a vertex whose <a href=""#eccentricity""><span title=""See entry on this page at § eccentricity"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">eccentricity</span></a> is maximum. In a tree, this must be a leaf.</dd>
"
Petersen (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  <a href=""https://en.wikipedia.org/wiki/Julius_Petersen"" title=""Julius Petersen"">Julius Petersen</a> (1839–1910), Danish graph theorist.</dd>
<dd class=""glossary"">2.  The <a href=""https://en.wikipedia.org/wiki/Petersen_graph"" title=""Petersen graph"">Petersen graph</a>, a 10-vertex 15-edge graph frequently used as a counterexample.</dd>
<dd class=""glossary"">3.  <a href=""https://en.wikipedia.org/wiki/Petersen%27s_theorem"" title=""Petersen's theorem"">Petersen's theorem</a> that every bridgeless cubic graph has a perfect matching.</dd>
"
planar (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Planar_graph"" title=""Planar graph"">planar graph</a> is a graph that has an <a href=""https://en.wikipedia.org/wiki/Graph_embedding"" title=""Graph embedding"">embedding</a> onto the Euclidean plane. A plane graph is a planar graph for which a particular embedding has already been fixed. A <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>-planar graph is one that can be drawn in the plane with at most <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> crossings per edge.</dd>
"
polytree (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Polytree"" title=""Polytree"">polytree</a> is an oriented tree; equivalently, a directed acyclic graph whose underlying undirected graph is a tree.</dd>
"
power (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/Graph_power"" title=""Graph power"">graph power</a> <span class=""texhtml""><i>G</i><sup><i>k</i></sup></span> of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is another graph on the same vertex set; two vertices are adjacent in <span class=""texhtml""><i>G</i><sup><i>k</i></sup></span> when they are at distance at most <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> in <span class=""texhtml mvar"" style=""font-style:italic;"">G</span>. A <a href=""https://en.wikipedia.org/wiki/Leaf_power"" title=""Leaf power"">leaf power</a> is a closely related concept, derived from a power of a tree by taking the subgraph induced by the tree's leaves.</dd>
<dd class=""glossary"">2.  <a href=""https://en.wikipedia.org/wiki/Power_graph_analysis"" title=""Power graph analysis"">Power graph analysis</a> is a method for analyzing complex networks by identifying cliques, bicliques, and stars within the network.</dd>
<dd class=""glossary"">3.  <a href=""https://en.wikipedia.org/wiki/Power_law"" title=""Power law"">Power laws</a> in the <a href=""https://en.wikipedia.org/wiki/Degree_distribution"" title=""Degree distribution"">degree distributions</a> of <a href=""https://en.wikipedia.org/wiki/Scale-free_network"" title=""Scale-free network"">scale-free networks</a> are a phenomenon in which the number of vertices of a given degree is proportional to a power of the degree.</dd>
"
predecessor (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""#vertex""><span title=""See entry on this page at § vertex"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">vertex</span></a> coming before a given vertex in a <a href=""#directed_path""><span title=""See entry on this page at § directed path"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">directed path</span></a>.</dd>
"
proper (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A proper subgraph is a subgraph that removes at least one vertex or edge relative to the whole graph; for finite graphs, proper subgraphs are never isomorphic to the whole graph, but for infinite graphs they can be.</dd>
<dd class=""glossary"">2.  A proper coloring is an assignment of colors to the vertices of a graph (a coloring) that assigns different colors to the endpoints of each edge; see <a href=""#color""><span title=""See entry on this page at § color"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">color</span></a>.</dd>
<dd class=""glossary"">3.  A <a href=""https://en.wikipedia.org/wiki/Proper_interval_graph"" class=""mw-redirect"" title=""Proper interval graph"">proper interval graph</a> or proper circular arc graph is an intersection graph of a collection of intervals or circular arcs (respectively) such that no interval or arc contains another interval or arc. Proper interval graphs are also called unit interval graphs (because they can always be represented by unit intervals) or indifference graphs.</dd>
"
property (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Graph_property"" title=""Graph property"">graph property</a> is something that can be true of some graphs and false of others, and that depends only on the graph structure and not on incidental information such as labels. Graph properties may equivalently be described in terms of classes of graphs (the graphs that have a given property). More generally, a graph property may also be a function of graphs that is again independent of incidental information, such as the size, order, or degree sequence of a graph; this more general definition of a property is also called an invariant of the graph.</dd>
"
pseudoforest (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Pseudoforest"" title=""Pseudoforest"">pseudoforest</a> is an undirected graph in which each connected component has at most one cycle, or a directed graph in which each vertex has at most one outgoing edge.</dd>
"
pseudograph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A pseudograph is a graph or multigraph that allows self-loops.</dd>
"
quasi-line graph (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A quasi-line graph or locally co-bipartite graph is a graph in which the open neighborhood of every vertex can be partitioned into two cliques. These graphs are always <a href=""https://en.wikipedia.org/wiki/Claw-free_graph"" title=""Claw-free graph"">claw-free</a> and they include as a special case the <a href=""https://en.wikipedia.org/wiki/Line_graph"" title=""Line graph"">line graphs</a>. They are used in the structure theory of claw-free graphs.</dd>
"
quiver (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Quiver_(mathematics)"" title=""Quiver (mathematics)"">quiver</a> is a directed multigraph, as used in <a href=""https://en.wikipedia.org/wiki/Category_theory"" title=""Category theory"">category theory</a>. The edges of a quiver are called arrows.</dd>
"
radius (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The radius of a graph is the minimum <a href=""#eccentricity""><span title=""See entry on this page at § eccentricity"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">eccentricity</span></a> of any vertex.</dd>
"
Ramanujan (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Ramanujan_graph"" title=""Ramanujan graph"">Ramanujan graph</a> is a graph whose spectral expansion is as large as possible. That is, it is a <span class=""texhtml mvar"" style=""font-style:italic;"">d</span>-regular graph, such that the second-largest eigenvalue of its adjacency matrix is at most <span class=""mwe-math-element""><span class=""mwe-math-mathml-inline mwe-math-mathml-a11y"" style=""display: none;""><math xmlns=""http://www.w3.org/1998/Math/MathML"" alttext=""{\displaystyle 2{\sqrt {d-1}}}"">
<semantics>
<mrow class=""MJX-TeXAtom-ORD"">
<mstyle displaystyle=""true"" scriptlevel=""0"">
<mn>2</mn>
<mrow class=""MJX-TeXAtom-ORD"">
<msqrt>
<mi>d</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</msqrt>
</mrow>
</mstyle>
</mrow>
<annotation encoding=""application/x-tex"">{\displaystyle 2{\sqrt {d-1}}}</annotation>
</semantics>
</math></span><img src=""https://wikimedia.org/api/rest_v1/media/math/render/svg/1f27a0c44bfbbbacc1abe00ca33bc5a529f7d5dd"" class=""mwe-math-fallback-image-inline"" aria-hidden=""true"" style=""vertical-align: -0.505ex; width:8.317ex; height:3.009ex;"" alt=""2\sqrt{d-1}""/></span>.</dd>
"
ray (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A ray, in an infinite graph, is an infinite simple path with exactly one endpoint. The <a href=""https://en.wikipedia.org/wiki/End_(graph_theory)"" title=""End (graph theory)"">ends</a> of a graph are equivalence classes of rays.</dd>
"
"<a href=""https://en.wikipedia.org/wiki/Reachability"" title=""Reachability"">reachability</a> (Wikipedia Glossary of Graph Theory Terms)"|"
<dd class=""glossary"">The ability to get from one <a href=""#vertex""><span title=""See entry on this page at § vertex"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">vertex</span></a> to another within a <a href=""#graph""><span title=""See entry on this page at § graph"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">graph</span></a>.</dd>
"
reachable (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Has an affirmative <a href=""#reachability""><span title=""See entry on this page at § reachability"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">reachability</span></a>. A <a href=""#vertex""><span title=""See entry on this page at § vertex"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">vertex</span></a> <span class=""texhtml""><i>y</i></span> is said to be reachable from a vertex <span class=""texhtml""><i>x</i></span> if there exists a <a href=""#path""><span title=""See entry on this page at § path"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">path</span></a> from <span class=""texhtml""><i>x</i></span> to <span class=""texhtml""><i>y</i></span>.</dd>
"
recognizable (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">In the context of the <a href=""https://en.wikipedia.org/wiki/Reconstruction_conjecture"" title=""Reconstruction conjecture"">reconstruction conjecture</a>, a graph property is recognizable if its truth can be determined from the deck of the graph. Many graph properties are known to be recognizable. If the reconstruction conjecture is true, all graph properties are recognizable.</dd>
"
reconstruction (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The <a href=""https://en.wikipedia.org/wiki/Reconstruction_conjecture"" title=""Reconstruction conjecture"">reconstruction conjecture</a> states that each undirected graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is uniquely determined by its <i>deck</i>, a multiset of graphs formed by removing one vertex from <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> in all possible ways. In this context, reconstruction is the formation of a graph from its deck.</dd>
"
rectangle (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A simple cycle consisting of exactly four edges and four vertices.</dd>
"
regular (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A graph is <span class=""texhtml mvar"" style=""font-style:italic;"">d</span>-regular when all of its vertices have degree <span class=""texhtml mvar"" style=""font-style:italic;"">d</span>. A <a href=""https://en.wikipedia.org/wiki/Regular_graph"" title=""Regular graph"">regular graph</a> is a graph that is <span class=""texhtml mvar"" style=""font-style:italic;"">d</span>-regular for some <span class=""texhtml mvar"" style=""font-style:italic;"">d</span>.</dd>
"
regular tournament (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A regular tournament is a tournament where in-degree equals out-degree for all vertices.</dd>
"
reverse (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#transpose""><span title=""See entry on this page at § transpose"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">transpose</span></a>.</dd>
"
root (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A designated vertex in a graph, particularly in directed trees and <a href=""https://en.wikipedia.org/wiki/Rooted_graph"" title=""Rooted graph"">rooted graphs</a>.</dd>
<dd class=""glossary"">2.  The inverse operation to a <a href=""https://en.wikipedia.org/wiki/Graph_power"" title=""Graph power"">graph power</a>: a <span class=""texhtml mvar"" style=""font-style:italic;"">k</span>th root of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is another graph on the same vertex set such that two vertices are adjacent in <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> if and only if they have distance at most <span class=""texhtml mvar"" style=""font-style:italic;"">k</span> in the root.</dd>
"
second order (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The second order <a href=""https://en.wikipedia.org/wiki/Logic_of_graphs"" title=""Logic of graphs"">logic of graphs</a> is a form of logic in which variables may represent vertices, edges, sets of vertices, and (sometimes) sets of edges. This logic includes predicates for testing whether a vertex and edge are incident, as well as whether a vertex or edge belongs to a set. To be distinguished from first order logic, in which variables can only represent vertices.</dd>
"
saturated (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#matching""><span title=""See entry on this page at § matching"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">matching</span></a>.</dd>
"
searching number (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Node searching number is a synonym for <a href=""#pathwidth""><span title=""See entry on this page at § pathwidth"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">pathwidth</span></a>.</dd>
"
self-loop (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Synonym for <a href=""#loop""><span title=""See entry on this page at § loop"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">loop</span></a>.</dd>
"
separating vertex (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">See <a href=""#articulation_point""><span title=""See entry on this page at § articulation point"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">articulation point</span></a>.</dd>
"
separation number (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">Vertex separation number is a synonym for <a href=""#pathwidth""><span title=""See entry on this page at § pathwidth"" class=""glossary-link-internal"" style=""border-bottom: 1px dashed #86a1ff; color:initial;"" id="""">pathwidth</span></a>.</dd>
"
simple (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">1.  A <a href=""https://en.wikipedia.org/wiki/Simple_graph"" class=""mw-redirect"" title=""Simple graph"">simple graph</a> is a graph without loops and without multiple adjacencies. That is, each edge connects two distinct endpoints and no two edges have the same endpoints. A simple edge is an edge that is not part of a multiple adjacency. In many cases, graphs are assumed to be simple unless specified otherwise.</dd>
<dd class=""glossary"">2.  A simple path or a simple cycle is a path or cycle that has no repeated vertices and consequently no repeated edges.</dd>
"
sink (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A sink, in a directed graph, is a vertex with no outgoing edges (out-degree equals 0).</dd>
"
size (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">The size of a graph <span class=""texhtml mvar"" style=""font-style:italic;"">G</span> is the number of its edges, <span class=""texhtml"">|<i>E</i>(<i>G</i>)|</span>.<sup id=""cite_ref-11"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-11"">[11]</a></sup> The variable <span class=""texhtml mvar"" style=""font-style:italic;"">m</span> is often used for this quantity. See also <i>order</i>, the number of vertices.</dd>
"
small-world network (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Small-world_network"" title=""Small-world network"">small-world network</a> is a graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other node by a small number of hops or steps. Specifically, a small-world network is defined to be a graph where the typical distance <i>L</i> between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodes <i>N</i> in the network <sup id=""cite_ref-12"" class=""reference""><a href=""https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#cite_note-12"">[12]</a></sup></dd>
"
snark (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A <a href=""https://en.wikipedia.org/wiki/Snark_(graph_theory)"" title=""Snark (graph theory)"">snark</a> is a simple, connected, bridgeless cubic graph with chromatic index equal to 4.</dd>
"
source (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A source, in a directed graph, is a vertex with no incoming edges (in-degree equals 0).</dd>
"
space (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">In <a href=""https://en.wikipedia.org/wiki/Algebraic_graph_theory"" title=""Algebraic graph theory"">algebraic graph theory</a>, several <a href=""https://en.wikipedia.org/wiki/Vector_spaces"" class=""mw-redirect"" title=""Vector spaces"">vector spaces</a> over the <a href=""https://en.wikipedia.org/wiki/GF(2)"" title=""GF(2)"">binary field</a> may be associated with a graph. Each has sets of edges or vertices for its vectors, and <a href=""https://en.wikipedia.org/wiki/Symmetric_difference"" title=""Symmetric difference"">symmetric difference</a> of sets as its vector sum operation. The <a href=""https://en.wikipedia.org/wiki/Edge_space"" class=""mw-redirect"" title=""Edge space"">edge space</a> is the space of all sets of edges, and the <a href=""https://en.wikipedia.org/wiki/Vertex_space"" class=""mw-redirect"" title=""Vertex space"">vertex space</a> is the space of all sets of vertices. The <a href=""https://en.wikipedia.org/wiki/Cut_space"" class=""mw-redirect"" title=""Cut space"">cut space</a> is a subspace of the edge space that has the cut-sets of the graph as its elements. The <a href=""https://en.wikipedia.org/wiki/Cycle_space"" title=""Cycle space"">cycle space</a> has the Eulerian spanning subgraphs as its elements.</dd>
"
spanner (Wikipedia Glossary of Graph Theory Terms)|"
<dd class=""glossary"">A spanner is a (usually sparse) graph whose shortest path distances approximate those in a dense graph or other metric space. Variations include <a href=""https://en.wikipedia.org/wiki/Geometric_spanner"" title=""Geometric spanner"">geometric spanners</a>, graphs whose vertices are points in a geometric space; <a href=""https://en.wikipedia.org/wiki/Tree_spanner"" title=""Tree spanner"">tree spanners</a>, spanning trees of a graph whose distances approximate the graph distances, and graph spanners, sparse subgraphs of a dense graph whose distances approximate the original graph's distances. A greedy spanner is a graph spanner constructed by a greedy algorithm, generally one that considers all edges from shortest to longest and keeps the ones that are needed to preserve the distance approximation.</dd>