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

2
votes
3answers
71 views

Prove that there is always a perfect match

Let Gn be a graph with 2n nodes: a0, a1, ..., an-1, b0, b1, ..., bn-1. Let the edges be formed like this: Node ai connects with bj and bk, where j = 2i mod n and k = (2i + 1) mod n Prove that ...
0
votes
0answers
19 views

Which dominations in graphs determined by st-connectivity?

Fundamentals of Domination in Graphs has 75 variations to domination. I am interested in domination determined by st-connectivity such as st-vertex-cuts. An example st-domination measure is Fussell-...
2
votes
1answer
52 views

Hamiltonian circuit in at least one component

I'm having trouble proving that the problem stated in the title is NP-complete, specifically by reduction from Hamiltonian circuit. Intuitively it's clear - Hamiltonian circuit in one graph is NP-...
1
vote
2answers
32 views

Assumption that graph is connected to prove Ore's Theorem

On Wikipedia, the Ore's Theorem says that if $G$ is a finite simple graph with $n \ge 3$ vertices and for all non-adjacent vertices $u$ and $v$, the sum of their degrees is greater than or equal to $n$...
2
votes
1answer
42 views

Graph-Theory: Find matching in bipartite graph

Let $G=(V,E)$ be a graph such that $V=X\cup A\cup B$ . $X,A,B$ are independent sets and pairwise disjoint. Suppose that $|X|=63,|A|=|B|=9$, the degree of every vertex in $A\cup B$ is 7, and every ...
2
votes
1answer
37 views

Equivalence relations on graphs

Consider the graph $G$. For edges $e_1,e_2 \in E(G),$ let $e_1 \sim e_2$ if either $e_1 = e_2$ or $e_1$ and $e_2$ lie on some common cycle in $G$. I want to be able to prove that $\sim$ is an ...
4
votes
1answer
38 views

Every planar graph is a union of $3$ forests

I am currently working on problems related to planarity in graphs, and I came across a peculiar problem related to proving the relationship between planar graphs and forests. Take a planar graph $P$. ...
2
votes
0answers
39 views

Graph theory - what is monotonie?

I have the following task but no idea on how to get the right result. It is about graphs and monotonic functions. The functions $\alpha$, $\beta$ are defined as $$\alpha(n,d) = \min \{m: G \text{ is ...
0
votes
0answers
7 views

Family relationships and random assignments

Suppose I deliver a special note to 2% of a population at random. What is the probability that such note has been delivered : parent and child cousin and cousin Assume a birth rate with a mean of ...
10
votes
0answers
2k views

Triangle dissection, no shared edges

It's possible to divide a triangle into smaller triangles such that no edge lengths are shared. Alternately, no two internal triangles share two vertices. The top three are the known simplest ...
4
votes
0answers
51 views

How to describe/name all the paths in an undirected graph where every node has no more than two neighbors?

I am modeling a road network as a graph, using GPS data, etc. A typical fraction of my graph would look like below: What I would like is to partition this graph as a list of node sequences, where ...
0
votes
0answers
30 views

Deducing MaxFlowMinCut from Menger

So the MaxFlowMinCut theorem with rational network capacities and (the edge-version of) Menger's theorem for undirected graphs are equivalent, both directions being not too hard. I gather that since ...
2
votes
2answers
20 views

Bound on chromatic numbers of union of graphs

If I have a vertex-set $V$ and two graphs $G, H$ on $V$, it is easy to show that the chromatic number $\chi (G \cup H) \leq \chi (G) \chi (H)$. My question now is, whether $\chi (G \cup H) \leq \chi (...
2
votes
2answers
40 views

Some doubts on the definition of minimality of a graph. EDITED

If a graph $G$ is minimal with property $P$, does that specifically mean: Any proper subgraph of $G$ does not have that property $P$? Or, Any graph with less number of vertices or less number of ...
0
votes
0answers
8 views

Are transactions across petri net assumed to be running in parallel or there is always a predefined order?

I have a place $P$ with 3 marks in it and two outgoing immidiate Transitions [$t1, t2$] that require 1 token to fire. How marks flow are determined in Petri Net? Are there any Petri Net flavour ...
4
votes
1answer
47 views

Directing graph such that any outdegree would be at most 2

Let $G=(V,E)$ graph. Suppose that for every subgraph $G'=(V',E') , G' \subset G, |E'| \le 2|V'|$. Show it's possible to direct G such that any outdegree would be at most 2. I tried proving it by ...
0
votes
0answers
15 views

$k$-vertex-critical graph which is not $k$-edge-critical

A graph like $G$ is called $k$-vertex-critical if $\chi(G)=k$ and $\forall v\in V(G)\space\chi(G-v)\lt\chi(G)$ where $\chi(G)$ is the vertex chromatic number of $G$. A graph like $G$ is called $k$-...
0
votes
0answers
14 views

Finding heavy independent sets

What are some good algorithms for finding maximum weight independent sets in a graph with vertex weights?
0
votes
0answers
88 views

Proof of the statement 'World is not flat' by graph theory [duplicate]

In my graph theory book exercise,I found a problem that: Prove that,World is not flat using Mathematics This picture is used in the exercise,but no idea of applying it.
4
votes
0answers
47 views

Graph has vertices 8 and without cycles of length 4

What is the maximum number of edges can be a simple graph with $8$ vertices, in which there are no cycles of length $4$? My work so far: Let $t (n) -$ response (number of edges) for a graph with $n$...
3
votes
2answers
37 views

If a graph is k connected, then is it k+1 connected or k-1 connected? Or none?

I am just wondering what can we conclude further if a graph is $k-\text{vertex}$ $-\text{ connected}$. This is just my personal doubt. Before that I want to clarify the definition: According to ...
1
vote
1answer
37 views

Prove : Each distinct $R_{k,e}$ can appear maximum $\sqrt b \leq n^{3}$ times.

Notation: $H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...
6
votes
1answer
264 views

Prove the statement 'World is not flat'

In my graph theory book exercise, I found a problem that: Prove that the World is not flat using Mathematics This picture is used in the exercise, but no idea of applying it. I would have ...
0
votes
0answers
27 views

How is named a certain family of probabilistic graphs with non classical information transfer

I have a graph $G$ with $n$ inter-connected nodes. Each node can have data points in it. The edge transfer costs are not important. Yet what is important is the fact that there is a probability ...
6
votes
0answers
62 views

fitting points into partitions of a square

A friend of mine came up with the following problem: Let $\{X_1, X_2, ..., X_n\}$ be an arbitrary finite partition of the unit square $[0, 1]^2$. Let $\{P_1, P_2, ..., P_m\}$ be a finite set of ...
0
votes
1answer
36 views

A game: When can you merge two directed graphs?

I am trying to consider the conditions under which you can win the following directed graph game: Graph merging game. Fix an acyclic directed graph $G$; its vertex set is $V$, and its edge set is $...
1
vote
1answer
34 views

Tree properties

I am reviewing Diestel's Graph Theory and we are asked to prove that the following are equivalent: (i) $T$ is a tree. (ii) Any two vertices of $T$ are linked by a unique path in $T$. (iii) $T$ is ...
0
votes
0answers
26 views

Probabalistic modeling of graph topology / network structure

I'll just let you know right now that I will be using very informal language here, so if you have other questions about technicalities that need to be specified please let me know. Let's say we have ...
2
votes
0answers
59 views

Toroidal spaces inside a sphere

I was studying wikipedia articles about toruses and genuses and I have following question. If we have a sphere (let's assume it is The Earth) and made a cylindrical passage through it (by drilling), ...
2
votes
0answers
39 views

Coloring (W-L Method)

I am trying to read An Optimal Lower Bound on the Number of Variables for Graph Identification. On page 3 (4th paragraph), it is written- It might color vertices and edges implicitly by using $k$-...
1
vote
0answers
16 views

Prove that bipartitle graph $G$ always has matching $M$, such that $ |M| >\frac{ |E(G)|}{ ∆(G)}$.

How to prove that bipartitle graph $G$ always has matching $M$, such that $ |M| >\frac{ |E(G)|}{ ∆(G)}$, where $E(G)$ is amount of edges and $∆(G)$ is maximal degree?
0
votes
0answers
10 views

How to prove criteria of vertex being not in all maximum matchings?

So, i know, next fact is correct, but don't really know, how to prove it: Let $M$ be matching of graph $G$, vertex $u$ is $M$ - unsaturated. Then, if there is no augmenting path for $M$, which starts ...
2
votes
2answers
22 views

Hamilton-connected graphs have a chromatic number at least 3

A Hamilton-connected graph is a graph where for every pair of vertices there exists a hamiltonian path that connects them. I'm trying to prove that the chromatic number of a Hamilton-connected graph $...
0
votes
2answers
24 views

Union of spanning forest is also spanning forest

We have one graph $G$ and we divided its edges on two graphs $A$ and $B$ (both of them have all nodes of graph $G$). Now, we compute spanning forest of each of new graphs. Is it true that for every $...
2
votes
1answer
35 views

Show that a 2k regular graph has a matching of size at least k-1

Let $H$ be a 2k-regular graph with $n=4k+1$ vertices (and thus $m=k(4k+1)$ edges). Show that $H$ has at least k-1 independent edges (or that there exists a matching of size at least k-1 in $H$). If ...
2
votes
1answer
23 views

strongly regular graph with vertices subset of {1,2,…,7}

I have the following homework question: Let G be the graph obtained as follows. Let A={1,2,...,7}. Let the vertices of G be all the subsets of A of size 3 and 2 vertices be adjacent if and only if ...
1
vote
0answers
18 views

Is there a minimum spanning tree including $e$ after removing at most $k$ edges?

Let an undirected, connected graph $G=(V,E)$ with the weight funciton $w:E\to \mathbb{R}$, an edge $e$, and $0<k\in\mathbb{N}$. Describe an algorithm determines if there are at most $k$ edges could ...
1
vote
2answers
20 views

Prove that every vertex of a 2-regular graph G lies on an exactly one circle

My only idea so far is that if a vertex $v$ would lie on more than one circle, i. e. on 2 circles, then those 2 circles must separate in some vertex in order to be different and that cannot be because ...
3
votes
4answers
72 views

How can ($A$ and $B$ $\implies$ $C$) and ($C$ and $B$ $\implies$ not $A$) together imply (not $A\iff B$)?

I encountered this two statements when I tried to understand the proof of Kuratowski Theorem. Any minimal nonplanar graph and it has no Kuratowski subgraphs, then it must be at least 3 connected. An ...
0
votes
0answers
17 views

What's the fastest algorithm for computing transitive reduction for a sparse DAG?

I know this is a Math site, but if anyone wants to add pseudocode, Javascript-looking pseudocode would be preferred. Edit: looks like this question would be better for math.stackexchange.com. Would ...
0
votes
0answers
26 views

Graph Consistency Proof

Let $G = (V, E)$ be a graph. Assume that $G$ is bipartite, consistent and each vertex $G$ has a degree in 2016. Let $v ∈ V$ and $H = (V - v, E - {e ∈ E: v ∈ e}).$ Show that the graph $H$ is consistent....
1
vote
1answer
21 views

Is the hypercube graph $Q_n$ k-factorable for k=modn?

Definition of k-factorable graph: https://en.wikipedia.org/wiki/Graph_factorization I have proved that a hypercube of any dimension has a perfect matching, thus also a 1-factorization. Can it be ...
0
votes
0answers
20 views

Prove that every maximal outerplanar graph has a 3-coloring

A maximal outerplanar graph is an outerplanar graph (which is a graph with a planar drawing with all vertices belonging in the outer face), where adding any edge would make it stop being outerplanar. ...
0
votes
0answers
9 views

Are Oriented Graphs Related to Oriented Matroids?

My professor said that oriented matroids make it easier to investigate things such as connectivity. Recall that an oriented graph is a digraph without multiple edges or loops. Now Are oriented graphs ...
1
vote
0answers
20 views

Subgraph with “dangling edges”?

I was wondering if there is a notion in graph theory where one can have a subgraph such that the endpoints of all of the edges in the subgraph are not necessarily included in the vertex set of the ...
1
vote
0answers
22 views

If G be k vertex critical is it k edge critical too?

G is k- vertex critical if and only if for every vertex such v $\chi(G-v) < \chi(G)$ as same we can define k edge critical note that we know if G be k edge critical it is k vertex critical too ...
1
vote
1answer
28 views

Simple explanation of Dijkstra's Algorithm?

Can anyone provide a simple explanation of Dijkstra's Algorithm? My text, discrete mathematics with applications by Susanna Epp provides a very complex explanation of the algorithm that I cannot seem ...
1
vote
2answers
31 views

Is Reliability Component a vertex?

The term component has a distinct definition in graph theory from vertex while the terms components and vertices can be mostly the same in Realiability Engineering, my intuition. So how is the term ...
0
votes
0answers
103 views

What kind of graph is the StackExchange?

Assuming that we have three distinct layers of nodes called Users, Questions & Answers, connected by the obvious way $(A)$, what kind of graph is the StackExchange? Do such graphs have special ...
1
vote
0answers
14 views

Why converting a minor of a graph into a subdivision is not always possible?

In my attempt to try to understand the Kuratowski's Theorem and the Wagner's Theorem, I encountered an article in Wikipedia where it is mentioned that converting a minor of a graph into a subdivision ...