Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

1
vote
1answer
53 views

Disorganization In Mathematics

I was just wondering why it is that there are so many overlapping and seemingly random terms in mathematics. For example, I'm learning graph theory and according to different notes or books, two edges ...
3
votes
1answer
14 views

What is the term of a component drawn surrounded by another component?

Having a drawing (see image) of an undirected graph $G=(V,E)$ where $V = \{A,B,C,D,E,F,G\}$ and $v \in V$ $E = \{\{A,B\},\{B,C\},\{C,D\},\{D,A\},\{D,E\},\{E,F\},\{F,G\},\{G,E\}\}$ each vertex $v$ ...
0
votes
0answers
23 views

finding complete subgraph of a graph

Is there any relation between number of nodes, edge probability and size of complete subgraph of a given graph
1
vote
2answers
40 views

Show, for every connected graph G of order 6 with four independent vertices, that either α(G)=5 or α′(G) ≥ 2. [on hold]

Show, for every connected graph G of order 6 with four independent vertices, that either α(G)=5 or α′(G) ≥ 2. a(G) stands for vertex independent number (max number of vertices such that no two ...
1
vote
1answer
30 views

Find number of vertices when given number of edges

A Simple Connected Graph G has $M$ vertices and 4 edges, find $M$ Now lets say we didn't have any more info than what's mentioned above. By drawing out a couple of graphs I know that $M$ could ...
-2
votes
1answer
48 views

Prove that if G is a graph of order n, maximum degree ∆, and having no isolated vertices, then β(G) ≥ n/(∆+1) [on hold]

Prove that if G is a graph of order n, maximum degree ∆, and having no isolated vertices, then β(G) ≥ n/(∆+1) β is the vertex covering number. It's the minimum number of vertices that cover all edges ...
0
votes
0answers
13 views

Vector elements converging to the same value - a proof by contradiction

Note: I'm going to simplify the proposition and proof in this question a bit to avoid a large number of definitions and theorems - hopefully I don't remove anything vital. I'm afraid the material here ...
2
votes
1answer
25 views

What do you call a directed graph in which reachablility is a symmetric relation?

Let $(N,E)$ a directed graph in which, if $a$ is reachable from $b$, then $b$ is also reachable from $a$. In other words, if $a$ and $b$ lie on a common path, then they also lie on a common cycle. ...
2
votes
0answers
11 views

Unusual graph measure

Integrated information theory of consciousness is a complex mathematical model of information transfer in neural networks. Some of its conclusions are obvious: neither fully disconnected nor the ...
1
vote
3answers
80 views

Are there any examples of Graphs in nature? [on hold]

When it comes to fractals, there are several examples we can point to and say 'this is a fractal', such as snowflakes, ferns, trees and coastlines. Are there any equally clear examples of graph and ...
0
votes
1answer
21 views

Intuition behind this algorithm for finding an Eulerian circuit in a graph?

An Eulerian circuit of a directed graph $G = (V,E)$ is a path that travels through every edge in $E$ exactly once. This algorithm finds such a circuit if it exists. (I am interested in the directed ...
2
votes
1answer
48 views

A Puzzle on Infinity: How to guess the color of hats? [duplicate]

Infinitely many (i.e. $\omega$ - many) people each have either a white hat or black hat on their heads. Each person can see everyone's hats except their own. Each person simultaneously announces a ...
1
vote
1answer
35 views

Show that $C_n\times K_2$ is $1$-factorable for $n\ge4$

Show that $C_n\times K_2$ is $1$-factorable (has a perfect matching) for $n\ge4.$ $\times$ means the Cartesian product. $C_n$ means a cycle where $n=$ number of vertices of the cycle. $K_2$ means the ...
1
vote
2answers
21 views

Constructing Turan Graphs

A "Turan Graph " on $n$ vertices is graph on $n$ vertices without triangles and with exactely $\lfloor \frac{n^2}{4}\rfloor$ edges. How many are the Turan Graphs on $8$ vertices? There's an easy ...
2
votes
2answers
32 views

Graph's Matching and edge covering

Let $G$ be a graph and $M$ a match with maximum size and $F$ an edge cover with minimal size. Prove that: $|M|+|F| = |V|$ That means that the number of all Matches with maximum size and the number of ...
-3
votes
1answer
33 views

Neighbourhood set in Graph theory [on hold]

Let $G$ be any connected graph with $\Delta(G)$ be maximum degree. If $D \subseteq V(G)$ then how can we say that $\left | \bigcup \limits_{v \in D} N(v) \right | \leq |D| \Delta(G)$.
3
votes
1answer
48 views

planarity of trivalent graphs with a cyclic ordering on the edges in each vertex

Let $G$ be an (undirected) trivalent graph. For each vertex $v$ of $G$ we choose a cyclic ordering on the edges coming into $v$ (so if vertex $A$ has neighbors $B, C$ and $D$ we decide whether the ...
1
vote
0answers
15 views

Matching vertices between two graphs

I have a situation where I have two graphs that are supposed to represent the same underlying topology but represent the underlying topology at different resolutions. My goal is to match vertices ...
0
votes
2answers
33 views

Prove or dis-prove that it always holds or not $\lambda(G) \leq \chi(G) $ [on hold]

I want to prove that this inequality holds or not? The inequality is $\lambda(G) \leq \chi(G) $ where $\lambda(G)$ is the minimum number of edges whose deletion from a graph $G$ disconnects $G$, ...
1
vote
1answer
26 views

How does the following graph have an Euler tour and not every node has degree that is even?

The theorem states: A connected graph has an Euler tour if and only if every vertex has even degree. But this graph has node 'A' with degree = 3. Graph image. ...
4
votes
1answer
75 views

Graph theory application of homology

I am struggling with the idea of local homology groups and would like to see an example of how to go about finding them in general. I'm thinking of the most trivial case to apply the theory of local ...
1
vote
1answer
30 views

How to find List Chromatic Number of planar graphs [on hold]

I want to know how we can find the list chromatic number of planar graphs, Suppose we have graph $G= K_{3}$. Then its chromatic number is $3$, but what is the list chromatic number of $K_{3}$? ...
5
votes
3answers
33 views

Any undirected graph on 9 vertices with minimum degree at least 5 contains a subgraph $K_4$?

Let $G$ be simple undirected graph with degree of every vertices is at least 5. Prove or disprove that $G$ contains subgraph $K_4$. I came up with this question when I were trying to find Ramsey ...
6
votes
0answers
142 views

A graph problem

Consider the following graph problem. We are given a set of vertices $A_i$, $B_i$, and $C_i$ where $i \in \{1,2,3 \}$. For each vertex, there is a corresponding weight where the weight of vertex $A_i$ ...
0
votes
3answers
26 views

Number of arcs in undirected graph

It is a basic question in graph theory! I have n nodes and I would like to calculate the number of paths among n nodes so that each node appears once in a path. I think it is Hamilton cycle, but I am ...
0
votes
0answers
20 views

Number of nodes satisfying a certain property on a binary tree

Fix a large integer $M$ and construct a binary tree as follows. Assign the root node by the integer $0$. If a node is assigned the integer $n$ and $n \leq M - 2$, then $n$ has two children and ...
3
votes
1answer
33 views

Does the complete graph contain the maximum number of simple cycles?

Let $\mathcal{G}(n,m)$ be the set of connected, simple graphs with $n$ vertices and $m$ edges. For any graph $G$ we denote its number of simple cycles with $\mu(G)$ and and for any finite family of ...
2
votes
2answers
1k views

counting simple, connected graphs

I've been thinking about this for a few days, but I haven't found a general solution yet. How many distinct simple, connected, undirected graphs are there of n labelled vertices? For example, there is ...
0
votes
0answers
24 views

Chinese Postman Problem - open walk variation

Consider the following variation of the Chinese postman problem (also known as the route inspection problem). Instead of finding the shortest closed walk which traverses each edge at least once, find ...
2
votes
1answer
151 views

ER graphs, expected number of triangles incident to one vertex

I'm really sorry for this question. I'm new to a graph theory, and I hope you will help me to understand one statement. Consider $ER(n,p)$ graph with $n \geq 3$ and $p \in [0,1]$. The statement ...
0
votes
0answers
23 views

Relationship between ST-Path Ideals and ST-Cut Ideals?

Topic: st-connectivity, st-cut ideals and path ideals of a graph My Lemma: None of the st-cut-monomials vanish iff there is at least a st-path that does not vanish. Example ST-cuts: {{1,3,5,6},{...
1
vote
1answer
70 views

Complete Graph with odd degree

It is known that the Complete Graph $K_n$ has $n^{n-2}$ spanning trees. The $K_{10}$ has $10^8$ spanning Trees. Now my question: How can I compute the number of spanning Trees with odd degree of its ...
0
votes
0answers
48 views

relationship between uniform Hypergraph maximum matching minimum vertex cover minimum clique partition

A k-$\bf{uniform}$ hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a size $k$ subset of $V$. (Note: ...
0
votes
1answer
23 views

Is the maximum size of a matching of graph equal to the maximum size of a matching of its dual?

This is really puzzling me! A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$. A ...
0
votes
0answers
27 views

Proof of Petersons theorem (less than 3 bridges) with Tutte's Theorem

Petersons Theorem: A 3-regular graph with at most 2 bridges has a perfect matching. My task is to prove this theorem by just using Tutte and not Tutte-Berge. My first general question: Are you ...
0
votes
1answer
15 views

Class of directed graph for which there is only one path to a given parent?

From a nomenclature standpoint, I am wondering if there is a name for a class of directed graph that has only one path to any given parent. I can visualize this shape as an upside down tree that may ...
0
votes
2answers
46 views

Prove that a graph has a cycle of length no more than $14$

A graph contains $2016$ vertices, its chromatic number is $5$, prove that this graph has a cycle of length $\leq 14$. Where do I start?
0
votes
0answers
8 views

Acyclic orientation of a mixed graph with minimization of the critical path

I already asked this question as a guest but I was not able to edit it or add comments after I registered with my e-mail address. A apologize for asking the same question again. A mixed graph is a ...
1
vote
1answer
29 views

If deg$(v) \geq k$ for all $v \in V(G)$, then G contains a matching of cardinality $\min \{k,\lfloor{\frac{|V|}{2}}\rfloor\}$

Let$G = (V; E)$ be an undirected graph. Show that if deg$(v) \geq k$ for all $v \in V$, then G contains a matching of cardinality $\min \{k,\lfloor{\frac{|V|}{2}}\rfloor\}$. I have no idea how to ...
0
votes
0answers
18 views

Principle of Duality on digraphs: dual properties?

Given an arc $uv$ of a digraph $D$, the dual $D'$ of the digraph $D$ has the arc $vu$. I am trying to find dual properties for digraphs. I could find a page 301 of document on Principle of Duality for ...
0
votes
0answers
16 views

Duality between cut ideals and cycle ideals?

There exist a general duality between vertex-cuts and cycles and also Duality Principle on Digraphs. I am trying to find a duality prienciple expressed in terms of ideals so Does there exist a ...
4
votes
2answers
2k views

A cardinality of a graph

If I have graph $G=(V,E)\\$ What is the meaning of $|G|$? (The cardinality of G). I'd like to few words about it... Thank you!
0
votes
0answers
36 views

How can i prove that the wiener index of a truncated wheel graph is 3n(5n - 6) where n is greater than or equal to 4? [closed]

A truncated wheel graph TW_n, n is greater than or equal to 3, is the graph with vertex set V(TW_n) = {v_0, v_{i,1}, v_{i,2}, v_{i,3} | i = 1, 2,..., n} and edge set E(TW_n) = {v_0 v_{i,1}, v_{i,1}v_{...
1
vote
0answers
37 views

How do I write a function that maps a variable to a set?

I have a function $\Gamma$ that maps elements from $N$ to a (possibly empty) subset of $N$. The number of elements in the resulting subset depends on which element of $N$ we are dealing with, i.e. $\...
4
votes
1answer
93 views

Probabilistic method: vertex disjoint cycles in digraphs

Let us say that a di-graph is $k$-regular if every vertex has precisely $k$ out-edges. The following theorem appears in a book I am currently studying Theorem. Every $k$-regular graph $D$ has a ...
0
votes
1answer
767 views

Dijkstra Algorithm proof

I was studying the proof of correctness of the Dijkstra's algorithm . In the above slide , $d(u)$ is the shortest path length to explored $u$ and $$\pi(v) = \min_{ e\ =\ u,v:u \in S}d(u) + l_e$$ and $...
1
vote
0answers
15 views

Citations for the proof of universality of graph classes

In Automorphisms of graphs, Peter J. Cameron mentioned following classes of graphs which are universal structures. graphs of valency k for any fixed k > 2; bipartite graphs; strongly regular graphs; ...
0
votes
0answers
12 views

Orient edges in a mixed graph to minimize the critical path

3 down vote favorite A mixed graph is a graph that has directed and undirected edges. Is there an efficient algorithm that allows the orientation of undirected edges in a mixed graph in such a way ...
0
votes
2answers
316 views

When a 0-1-matrix with exactly two 1’s on each column and on each row is non-degenerated? [1]

Let $A$ be an $n\times n$ matrix with entries in the set $\{0,1\}$ which has exactly two ones in each column and two ones in each row. Give necessary and sufficient conditions for the rank of $A$ to ...