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
38 views

Proof: How many edges need be removed from this graph to produce the spanning tree?

Assume the graph,$G$ has the degree sequence $6,4,4,3,3,3,3,2,2$. How many edges must be removed from $G$ to produce the spanning tree $T$? We can construct this graph using Havel-Hakimi's ...
0
votes
0answers
18 views

Proof verification that two spanning tress of the same graph are the same size

Let $H$ be any graph and $T_1$ and $T_2$ be spanning trees for $H$. Prove that the size of $T_1$ equals the size of $T_2$. Proof: $T_1$ has an edge set ...
0
votes
1answer
22 views

Prove that if $G$ is an nontrivial connected graph with at most 2 bridges, then there exists an orientation $D$

According to theorem 3.4, a nontrivial graph G has a strong orientation if and only if G is connected and contain no bridges a)Prove that if $G$ is an nontrivial connected graph with at most 2 ...
1
vote
1answer
46 views

Counting the number of complete bipartite subgraphs

I am stuck with problem and not getting much ideas. I have a graph with $N$ vertices and $M$ edges. I have to count number of ways I can choose a pair of set of vertices say $(p,q)$, such that every ...
0
votes
1answer
19 views

Orientation digraph question

Let $G$ be nontrivial connected graph without bridge a) show that for every edge $e$ of $G$ and for every orientation of $e$, there exist an orientation of the remaining edges of $G$ such that the ...
2
votes
0answers
25 views

Prove that a graph $G$ has an Eulerian orientation if and only if $G$ is Eulerian

Prove that a graph $G$ has an Eulerian orientation if and only if $G$ is Eulerian Here is what I got so far. => Let $G$ has an Eulerian Orientation, then $G$ is an Eulerian digraph. For any digraph ...
0
votes
0answers
10 views

Problem with finding max edge weighted subgraph in a complete graph, relative to it's node number

Let's sat that I have a complete, undirected, edge-weighted graph, and that I'm interested in finding the max-weight subgraph with regards to it's vertex set cardinality. Is there a specific name for ...
3
votes
1answer
30 views

Serial version of Hall's marriage theorem?

Hall's marriage theorem states that a collection of men can get married iff for every group of $k \geq 1$ men, the total number of women that like one or more of them is at least $k$. For example, if: ...
0
votes
0answers
25 views

Interesting inequality involving sets of points

I have the following result in a paper with no proof provided so I'm trying to construct one and wanted to question the validity of it. Some information in the paper maybe irrelevant to the proof ...
2
votes
4answers
654 views

What if not connectedness defines a graph?

I am studying graphs through an online course and came across the idea of a "connected component", a "subgraph in which any two vertices are connected to each other by paths, and which is connected to ...
3
votes
2answers
39 views

how many walks go through a given edge

Assume a symmetric matrix g of $0$'s and $1$'s that represents a non-directed graph with N nodes and assume there is an edge between nodes $i$ and $j$ (i.e. $g_{ij} = 1$). I am trying to count how ...
0
votes
1answer
20 views

Are These Graphs Circulant?

We will say a circulant graph is a graph whose adjacency matrix is circulant (even if the graph is disconnected). Let $R$ be a Dedekind domain, and let $I$ be an ideal of $R$ such that $R/I$ is finite ...
1
vote
1answer
18 views

Vertex degree and graph isomorphism

Suppose I have two simple graphs $G(V,E)$ and $H(V,E)$ with number of vertices $N$. And $\forall i \quad \text{such that}\quad 0<i<N$ No:of elements in $V(G)$ with degree $i $ = No:of elements ...
12
votes
1answer
70 views

What is the minimum number of vertices needed to represent a solid of genus $n$ in $\Bbb R^3$?

The image below shows a $9$-vertex polyhedron that is topologically equivalent to a torus, and hence has genus $1$. ...
1
vote
0answers
37 views

How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
0
votes
1answer
23 views

Relation between nodes in a graph

i'm currently working on a mathproblem in "discrete mathematics for computing". I'm a little behind and have some trouble with one question. "Let ∼ be a relation defined on the nodes on a graph G(N, ...
1
vote
0answers
25 views

An Eulerian graph without an arbitrary trail is connected?

Let $G=(V,E)$ be an Eulerian graph. We say that a vertex $v$ in $V$ is a generator if every trail beginning in $v$ can be extended to form an Eulerian circuit. For this we will only consider simple ...
0
votes
1answer
47 views

For n≥3, n set of boys and girls has a stable matching (true or false)

For some n ≥ 3 there exists a set of n boys, n girls, and preference lists for every boy and girl such that every possible boy-girl matching is stable. If true, give a proof. If false, give a ...
0
votes
0answers
34 views

Hadwiger's Conjecture for $k=1,2,3,4$

How can we show Hadwiger's Conjecture is true for $k=1,2,3,4$? Every $k$-chromatic graph $G$ has $K_k$ as a minor.
0
votes
1answer
32 views

Show this tree exists for n >= 3

I wonder if you guys can help me find an easier solution for this. Show that for every n >= 3 a tree exists with exactly n nodes and n - 1 leaves. My instructor had a solution that basically ...
0
votes
3answers
38 views

Chess Board Coloring of a Paper using an Arbitrary Curve

Pick a piece of paper and a pen. Put the pen on a starting point and begin to draw an arbitrary curve and don't withdraw your hand until you reached the starting point. You can meet your curve during ...
1
vote
1answer
124 views

Bipartite Graph Matching Proof

You have a bipartite graph where the vertices are partitioned into 10 boys and 20 girls. Every boy vertex has degree 6. Every girl vertex has degree 3. Show that there exists a matching that matches ...
0
votes
0answers
27 views

mapping functions for power set graphs

Let $G(\mathcal{P}(n),E)$ be a power set graph for $[n]$ elements with the inclusion relation. The width of such graph is known by Sperner's theorem $w=\binom{n}{n/2}$. By Dilowrth's theorem we can ...
2
votes
1answer
31 views

Why can the complete graph $K_{16}$ be partitioned into three copies of the Clebsch graph?

The Clebsch graph is a $5$-regular graph on 16 vertices, defined as follows. Take the vertices and edges of the $4$-cube, and then add edges between antipodal pairs of vertices. Apparently, the edges ...
0
votes
0answers
34 views

What is the maximum number of automorphisms for a connected cubic graph with $n$ nodes?

The maximum number of automorphisms for a connected cubic graph with $4,6,8,10,12,14,16$ nodes is $24,72,48,120,64,336,384$. Is there a formula to calculate the number for a given $n$ , or at least ...
0
votes
0answers
17 views

Understanding minimum cuts and normalized minimum cuts in a graph.

I came across minimum and normalized minimum cuts while reading about image segmentation using graphs. I can't seem to understand these two notions. It will be great if someone can explain these two ...
0
votes
0answers
23 views

.Demonstrate that a support graph of a strongly-connected digraph which doesn’t have odd circuites, is a bipartite graph.

Demonstrate that a support graph of a strongly-connected digraph which doesn’t have odd circuites, is a bipartite graph.
1
vote
1answer
39 views

Mutually Exclusive Definitions of Isomorphism?

Wolfram MathWorld defines Isomorphism: Let $V(G)$ be the vertex set of a simple graph and $E(G)$ its edge set. Then a graph isomorphism from a simple graph G to a simple graph H is a bijection ...
0
votes
1answer
52 views

A graph with infinitely many distinct cycles

I am trying to show the following statement, but I can't. If a graph contains infinitely many distinct cycles then it contains infinitely many edge-disjoint cycles.
0
votes
0answers
11 views

Contracted onto $K_t$

We say that $G$ can be contracted onto $K_t$ if $K_t$ can be obtained from $G$ by contracting edges (deleting any resulting loops and parallel edges). Let $G$ be a graph with $χ(G) = t ≤ 4$. Prove ...
0
votes
2answers
64 views

Is there a problem more difficult than NP-complete in graph theory?

There are some decision problems being NP-complete in graph theory, including the problem of deciding if a graph has a hamilton cycle, or determing the chromatic number. Since the number of labeled ...
0
votes
0answers
4 views

Network theory: reverse process to diffusion?

I'm interested in studying network theory and dynamic processes over graphs. In particular, I'm interested in small-world graphs. My question is, what would be the "reverse" process of diffusion? If ...
3
votes
1answer
119 views

Suppose that every vertex of $G$ has degree at least 3. Prove that $G$ has a cycle of even length.

I've been working through some graph theory problems and recently encountered one which had me stumped. Fortunately, a solution was provided by my resource. Unfortunately, the solution does not seem ...
2
votes
2answers
35 views

Determine a formula for the number of triangles in the line graph $L(G)$ in term of quantities in $G$

Determine a formula for the number of triangles in the line graph $L(G)$ in term of quantities in $G$ I know that the line graph $L(G)$ of $G$ is a graph whose vertices are one to one correspondence ...
1
vote
1answer
30 views

Show that if $G$ is a connected graph of order $n≥2$ and $k$ is an integer with $1≤k≤n-1$, then $G^k$ is $k$-connected.

Show that if $G$ is a connected graph of order $n≥2$ and $k$ is an integer with $1≤k≤n-1$, then $G^k$ is $k$-connected. I'm not sure if I'm on the right track, but I tried to prove this by induction ...
2
votes
0answers
57 views

Spanning tree with infinitely many chords.

First, let me remind chord of graph. An edge which joins two vertices of a cycle but is not itself an edge of cycle is chord of that cycle. Now, I want to show that if a graph has spanning tree with ...
0
votes
1answer
13 views

Connecting nodes under certain conditions and trying to find the correct sequence on OEIS to describe the situation.

I would like to construct graphs under the following conditions: No loops Maximum of one edge between any nodes Connected No intersection between the edges may occur on a plane. Now, a similar ...
1
vote
1answer
76 views

Paper claiming a graph isomorphism that isn't actually an isomorphism?

This seems like it shouldn't be a problem, but here we are. In 'McKay’s Canonical Graph Labeling Algorithm': http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf on page 6, we have figure 1, a ...
1
vote
1answer
17 views

Smallest non-isomorphic graphs with the same characteristic polynomials of their laplacian matrices

For isomorphic graphs, the characteristic polynomials of their laplacian matrices coincide, but the converse is not true. The characteristic polynomial of the laplacian matrix does not uniquely ...
0
votes
0answers
26 views

Upto which number of vertices does every graph have a name?

I have heard of many families of graphs and also many famous graphs named after persons who intensively studied it. But I did not find a complete list with the names of the graphs to, lets say, ...
1
vote
1answer
17 views

Determine all connected graph $G$ such that subdivision graph $S(G)$ is Hamiltonian

Determine all connected graph $G$ such that subdivision graph $S(G)$ is Hamiltonian The subdivision graph $S(G)$ of a graph $G$ is that graph obtained from $G$ by replacing each edge $e=uv$ of $G$ ...
1
vote
1answer
28 views

Determine the formula for the toughness of a tree

Determine the formula for the toughness of a tree Here is what I got so far. Since every tree $T$ has at least 2 leaves, if we remove any vertex that adjacent to one of these leaves, we will get a ...
3
votes
4answers
47 views

Prove $\chi(G)\chi(\bar{G}) \geq n$ for chromatic number of graph and its complement

Let us denote by $\chi(G)$ the chromatic number, which is the smallest number of colours needed to colour the graph $G$ with $n$ vertices. Let $\bar{G}$ be the complement of $G$. Show that (a) ...
0
votes
1answer
18 views

Investigating properties of complements of paths

Take the first $n$ natural numbers. Construct a vertex-labeled graph with a vertex for each number. Now, connect any two vertices $a,b$ with an edge iff $a \pm 1 \neq b$. As Perry Iverson pointed ...
1
vote
0answers
43 views

Graph problem…

Let $D=(V,A)$ be a directed graph, and $s,t \in V$. Let $f:A \to \mathbb{R}_+$ be an $s$-$t$ flow of value $\beta$, show that there exists an $s$-$t$ flow $f':A\to\mathbb{Z}_+$ of value ...
1
vote
1answer
42 views

What is the chromatic index of a complete graph with its edges doubled?

If $G$ is a graph, let $G'$ denote the graph obtained by doubling each edge of $G$. How can I show that $\chi'(G')=2\chi'(G)$? I am considering the two cases when $G$ is a complete graph $K_n$ with ...
0
votes
0answers
26 views

Theorem (Cayley). τ (G)= τ (G-e) +τ (G.e) where τ (G) number of spanning tree of G what is the proof of this theorem

Theorem (Cayley): $\tau (G)= \tau (G-e) +\tau (G/e)$, where $\tau(G)$ is the number of spanning trees of $G$. What is the proof of this theorem?
0
votes
0answers
16 views

Finding the size or bounds of a finite set from families of maps into it

Given a finite set $X$ with $x$ elements and a set $K$ with $k$ elements and knowing that there are $n$ families of functions $K \rightarrow X$, each of which has at most $2^x$ distinct functions, can ...
1
vote
2answers
35 views

Prove that no bipartite graph of order $3$ or more is Hamiltonian connected

Prove that no bipartite graph of order $3$ or more is Hamiltonian connected A graph $G$ is Hamiltonian connected if for every pair $u,v$ of vertices of $G$, there is a Hamiltonian $u-v$ path in ...
1
vote
1answer
13 views

Show that for every non-negative rational number $r$, there exist a graph $G$ with $t(G)=r$

a) Determine the toughness of the compete $k$-partite graph $ K_{n_1,n_2,…,n_k }$ where $n_1≤n_2≤⋯≤n_k$ b) Show that for every non-negative rational number $r$, there exist a graph $G$ with ...