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
0answers
18 views

Can a circuit in graph theory use a edge twice in the circuit

I need to find out a circuit in a graph that uses the edge ab, what I want to know is can the circuit use the edge ab, more than once.
1
vote
0answers
31 views

Maximization problem on a graph

Consider a graph $G(V,E)$. Let degree of each vertex be denoted to $\beta(v) < d$. Maximize the following, where $\beta(v)$ is the only variable for all vertex $v\in V$. $$ \max \sum_{(u,v)\in E} ...
0
votes
1answer
49 views

Attaching the numbers to the polygon

Suppose a regular 45-sided polygon and numbers 0,1,2,...,9. Now attach these numbers to vertices of the polygon such that for any arbitrary pair of numbers (among of 0 to 9) there exist a edge of the ...
1
vote
1answer
36 views

random graph models

What is the difference between G(n,m) and G(n,p)? In G(n,m) one picks m of the $n \choose2$ edges at random. In G(n,p) each of the $n \choose 2$ edges are present independently with probability p. ...
1
vote
1answer
91 views

Is there an efficient way for finding the chromatic number of a given graph?

On an exam, I was given the Peterson graph and asked to find the chromatic number and a vertex coloring for it. I spent quite some time playing around with different colorings and incorrectly ...
0
votes
2answers
60 views

Restriction on Graph Automorphism

This question referes to a definition in Eugene M. Luks paper "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time" (1981), page 48, available at ...
0
votes
1answer
712 views

How to find the number of vertices in a graph?

Suppose that a connected planar graph has 30 edges. If a planar representation of this graph divides the plane into 20 faces, how many vertices does this graph have? I am not sure how to get started ...
1
vote
0answers
224 views

Is D.B.West's Introduction to Graph theory a good book to start?

I am studying for International Olympiad for Informatics (IOI) and I have to have a good understanding of Graph Theory . a teacher suggested reading Introduction to Graph Theory by D.West. Is it a ...
1
vote
2answers
139 views

Graph Theory question?

Assuming that friendship is always mutual, prove that in any group of n  2 persons, there are at least 2 persons with the same number of friends in the group. How do I answer this question with a ...
1
vote
0answers
49 views

applications of product graphs

I was reading a book http://imrich.at/books/handbook-of-product-graphs-second-edition/. Under the section Preface it was written that: large networks such as the Internet graph, with several ...
1
vote
1answer
47 views

Bounds on the size of the arc set of a directed graph which is connected but not strongly connected

An exercise in Introduction to Graph Theory by Robin J. Wilson asks for a proof that, if $D$ is a simple directed graph with $n$ vertices and $m$ arcs which is connected but not strongly connected, ...
0
votes
2answers
77 views

Proving graph theory using induction

How would I go about proving that a graph with no cycles and n-1 edges (where n would be the number of vertices) is a tree? I am just really confused about where to start. Thanks in advance.
1
vote
1answer
51 views

Converting a graph to a biparte to find the maximal matching

Im trying to get the maximal matching via trial and error (for the matching problem) derived from the following graph: But before I do this, I know I need to convert it into a biparte graph? Ive ...
14
votes
6answers
934 views

Can an algorithm be part of a proof?

I am an undergraduate student. I have read several papers in graph theory and found something may be strange: an algorithm is part of a proof. In the paper, except the last two sentences, other ...
0
votes
1answer
105 views

Non-isomorphic labeled forests [closed]

Prove that the number of non-isomorphic labeled forests on the vertex set [n] is at least p(n) (the number of partitions of the integer n).
2
votes
0answers
80 views

How do you specify a link to a blind combinatorialist?

Regular projections of links look like graphs in the plane. So I'm wondering if it would be possible to specify a link up to isotopy with purely combinatorial data about this graph. If so, what kind ...
1
vote
2answers
113 views

Drawing a simple connected graph with certain criteria

Draw a simple graph G with 8 vertices that satisfy all of the conditions listed below: each vertex has a degree of at least 3 the graph is not regular meaning not all vertices have same degree the ...
1
vote
1answer
137 views

Adjacency Matrices

Can someone explain adjacency matrix's in simple terms? I'm not grasping the material from the text at all, and can't solve the sample solutions provided.such as k2,k3 and the reverse. I understand ...
1
vote
0answers
43 views

Family of sets. Directed acyclic graph representation.

We are given a family of sets $F=\{F_1,\ldots,F_n\}$ with each $F_i$ being a subset of a ground set $N=\{1,\ldots,n\}$. In addition, we assume for each $F_i$ that it's not the subset of another $F_j$ ...
0
votes
2answers
112 views

Euler & Hamiltonian Cycles

How would one illustrate a graph that has both an Euler cycle and a Hamiltonian cycle, but they are not the same? From what I read, the Euler cycles themselves must have included edges and vertices, ...
0
votes
1answer
33 views

Road and candidiate problem

The city has n districts and n - 1 bidirectional roads. We know that from any district there is a path along the roads to any other district. Let's enumerate all districts in some way by integers from ...
1
vote
2answers
157 views

Maximally connected planar graph

Let $G$ be a planar graph. Is it true that: (1) $G$ is a subgraph of a maximally connected planar graph. (2) If $G$ is a maximally connected planar graph with more than four vertices, then all ...
2
votes
3answers
808 views

Drawing a simple graph with a certain number of vertices

I am supposed to see if it is possible to draw a graph with 8 vertices given the degree sequence: 1,1,2,3,5,5,6,7 First I tried the handshaking lemma and it holds. So since drawing that graph is ...
4
votes
0answers
88 views

$f$-factors and fractional $f$-factors and odd cycles

For a graph $G=(V,E)$ and a nonnegative integer valued function $f$ defined on $V$, an $f$-factor of $G$ is a spanning subgraph $F\subseteq G$ such that $d_F(v)=f(v)$ for all $v\in V$. A fractional ...
1
vote
1answer
190 views

k critical graph cannot have k + 1 vertices

$k$-chromatic graph is called $k$-critical if removal of any vertex from graph makes it $k - 1$ vertex colorable. Now i have to prove that if $G$ is a $k$ critical graph then it cannot have $k+1$ ...
2
votes
1answer
203 views

Graph Colouring - Eulerian Path

I am doing some studying for a test I have in my discrete math class and I have come across this question which I am very stuck on and keep seem to find any help... If you draw a closed curve in a ...
0
votes
1answer
64 views

Vertices of a complete graph $K_6$ are painted in black and white: find a subgraph $K_3$ with vertices of the same color

Vertices of a complete graph $K_6$ are painted in black and white. Show that it contains a subgraph $K_3 \subset K_6$ with vertices of same color. I am quite newbie at discrete maths. So, any help ...
12
votes
2answers
1k views

Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
3
votes
3answers
157 views

Show that every graph can be embedded in $\mathbb{R}^3$

Show that every graph can be embedded in $\mathbb{R}^3$ with all edges straight. (Hint: Embed the vertices inductively, where should you not put the new vertex?) I've also received a tip ...
6
votes
1answer
287 views

How to get from Chebyshev to Ihara?

I have competing answers on my question about "Returning Paths on Cubic Graphs Without Backtracking". Assuming Chris is right the following should work. Up to one thing: The number of returning paths ...
1
vote
2answers
1k views

How many four-vertex graphs are there up to isomorphism;

Let us call graphs $G = (V,E)$ and $G' = (V', E')$ fundamentally different if they are not isomorphic. How many fundamentally different graphs are there on four vertices? This is a question on my ...
4
votes
1answer
192 views

Graph theory & Feynman integrals

I am attending a course in Graph Theory and I am interested learning something about applications of this subject to Physics, especially I would like to learn something about Feynman integrals. Could ...
7
votes
1answer
228 views

Combinatorial Interpretation of Graph Theoretical Relation Involving Chebyshev Polynomials

Given a graph $G$ and its adjacency matrix $A$. The $(i,j)$-th element of $A^r$ gives the number of ways to get from vertex $i$ to $j$ in $r$ steps (including backtracking). Now, the number of ...
0
votes
2answers
48 views

Find a graph with an adjacency matrix consisting $0$

(okay, I'm not learning math in english, so please don't be harsh with me for not using the correct terminology here, but I hope you can understand my problem. also feel free to correct me) Find a ...
2
votes
0answers
210 views

Hall's marriage theorem explanation

I stumbled upon this page in Wikipedia about Hall's marriage theorem: The standard example of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For ...
1
vote
2answers
87 views

Are these graphs Isomorphic

please consider this two graphes. G1: G2: Are they Isomorphic? Is G1 a planer graph? It contains a K 3,3 or k5? thanks alot
6
votes
3answers
204 views

How much topology for graph theory?

I am writing a thesis in the context of descriptive complexity in theoretical computer science and therefore need to study a little bit of graph theory. My background is not mathematics but computer ...
4
votes
1answer
102 views

Finding a tight upperbound

A call graph $G = \{V,E\}$ on phone metadata has a vertex $v \in V$ for each phone number and an edge $\{v,w\} \in E$ if there has been a phone call between $v$ and $w$. One can monitor calls of a set ...
0
votes
2answers
66 views

when can you say a complete graph has an L-coloring?

i think in general, for an arbitrary graph to have an L-coloring is NP-completeness. but when can you say a complete graph has an L-coloring?
0
votes
0answers
37 views

Proving if a graph is bipartite [duplicate]

Definition: A graph G=(V,E) can be coloured with k colours if ∀v∈V, v is assigned exactly one of k colours and ∀e=(u,v)∈E, u and v are coloured with different colours. Prove that a graph G=(V,E) is ...
1
vote
1answer
96 views

Of Face and Circuit Rank

The circuit rank of a graph $G$ is given by $$r = m - n + c,$$ where $m$ is the number of edges in $G$, $n$ is the number of vertices, and $c$ is the number of connected components. ...
0
votes
1answer
104 views

Compute eigenvalues of a regular graph.

I have a $(q^2+q)(q+1)$-regular graph. Is there some general method to compute the eigenvalues of the adjacency matrix of a $k$-regular graph explicitly? Or could we estimate its eigenvalues? Thank ...
0
votes
3answers
203 views

Show two graphs are not isomorphic

I know this graphs are not isomorphic. However they have the same number of vertex and edges, and the same degree sequence, is not the most easy case. If im correct, the graphs are isomorphic if ...
1
vote
1answer
77 views

Number of $r$-regular, triangle-free graphs of order 100

I would like to find a formula for the number of $r$-regular, triangle free graphs of order 100 where every non-adjacent pair of adjacent vertices has $a$ common neighbors. There is one special case ...
0
votes
1answer
15 views

Question about notation

I would like to know what $G\cup \left\{v \right\}$ means. Does it mean to tack on another vertex to the graph $G$ by placing all possible edges between $v$ and the vertices of $G$?
1
vote
2answers
139 views

Drawing Graph on 5 vertices.

Draw a graph on 5 vertices that contains no clique of size three (that is, no triangle) and no anti-clique of size three (that is, three vertices none of which is connected to any other). Here ...
1
vote
3answers
239 views

Show that there is exactly one maximal element in a poset with a greatest element?

This is true, any idea how to say it in proof form? I would guess: In a poset with one maximal element, then that element has no other elements above it and has elements below it. If its the only ...
0
votes
1answer
135 views

Finding minimal number of vertices which connect a graph

I'm doing some graph theory studying on my own and I encountered a problem. I have a connected graph $G$ of $11440$ edges and an unknown number of vertices. What would be the best algorithm to find ...
2
votes
1answer
92 views

Planar Realization of a Graph in Three-Space

We call a planar graph one that we can draw in two-space such that no two edges intersect. I was told that we're not so interested in drawing graphs in three-space, because it is "intuitively obvious" ...
2
votes
3answers
224 views

Bounds on the chromatic number of a directed graph given bounds on out degree.

We defined a coloring of a directed graph to be equivalent to the coloring of the undirected graph with the same edges. The problem asks us to show if $\deg^+(v)\leq k$ for all $v \in V(G)$, then ...